Description：

给一个正整数序列，判断他的每个子区间是否都存在一个在这个子区间中只出现过一次的数。

$1\leqslant n\leqslant200000$

Solution：

分治真是解决区间问题的好工具。

首先一个区间如果存在一个数 $a[i]$ 它上一个和下一个都在区间外，那么所有跨过这个点的区间都是可以的，也就是剩下的只用考虑左右端点都在 $[l,i-1]$ 和 $[i+1,r]$ 的区间就可以了，那就可以分治，找出来一个这样的位置分治左右两边就行了。

但是时间复杂度 $T(n)=T(k)+T(n-k)+O(n)\Longrightarrow O(n^2)$ 。

注意到有一个定理是 $T(n)=T(k)+T(n-k)+O(min(k,n-k))\Longrightarrow O(n\log n)$ 。

所以只要从两边向内扩展，扩展到一个合法的位置就分治，这样复杂度就是对的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;

#define MAXN 200010

int a[MAXN],b[MAXN];

int pre[MAXN],nxt[MAXN];

int last[MAXN];

bool solve(int l,int r)

{

	if(l >= r)return true;

	for(int i = l,j = r;i <= j;++i,--j)

	{

		if(pre[i] < l && nxt[i] > r)return (solve(l,i - 1) & solve(i + 1,r));

		if(pre[j] < l && nxt[j] > r)return (solve(l,j - 1) & solve(j + 1,r));

	}

	return false;

}

void work()

{

	n = rd();

	for(int i = 1;i <= n;++i)a[i] = rd();

	for(int i = 1;i <= n;++i)b[i] = a[i];

	sort(b + 1,b + 1 + n);

	int tot = unique(b + 1,b + 1 + n) - b - 1;

	for(int i = 1;i <= n;++i)a[i] = lower_bound(b + 1,b + 1 + tot,a[i]) - b;

	for(int i = 1;i <= tot;++i)last[i] = 0;

	for(int i = 1;i <= n;++i)

	{

		pre[i] = last[a[i]];

		last[a[i]] = i;

	}

	for(int i = 1;i <= tot;++i)last[i] = n + 1;

	for(int i = n;i >= 1;--i)

	{

		nxt[i] = last[a[i]];

		last[a[i]] = i;

	}

	if(solve(1,n))puts("non-boring");

	else puts("boring");

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}