Solution
记序列为(a)，计算出与(a_i)相等的前一个元素的位置(pre_i)，以及后一个元素的位置(nex_i)，显然，对于那些左端点处于((pre_i,i])以及右端点处于([i,nex_i))的区间都可以认为是合法的。
那么我们可以将每个区间([l,r])抽象成一个二维平面的点((l,r))，每一个元素可以使得一部分区间合法，可以抽象为一个横坐标范围为([pre_i+1,i])且纵坐标范围为([i,nex_i-1])的矩形。对所有矩形进行求交，如果矩形覆盖了所有的合法点（也就是一个上三角形），那么序列就是合法的，否则不合法。
但是这样跑的非常慢！在BZOJ上AC的扫描线代码在我们OJ上是完全被卡常的.....有没有更加简便的做法？
考虑(check(l,r))表示所有左右端点处于([l,r])的区间是否合法。则答案就是(check(1,n))。
枚举(iin[l,r])，一旦找到一个(i)使得(pre_i<l)且(nex_i>r)，就停下。如果找不到，显然序列([l,r])本身就不合法，直接返回(false)。此时我们直接可以得知，左端点处于([l,i])且右端点处于([i,r])的区间全部是合法的！还剩下左右断电都处于([l,i))或((i,r])的区间未检查，返回(check(l,i-1)&&check(i+1,r))即可。
但是枚举这一步的复杂度我们没有保证，最坏总复杂度会达到(O(n^2))。我们需要一个思想：从两头向中间同时推进枚举，直到遇到第一个所需点为止。
时间复杂度是(T(n)=max{T(i)+T(n-i)+min(n,n-i)}=O(nlg n))。
为什么呢？感性地讲，如果把递归步骤倒过来看，就是一个启发式合并！关键就在(min(n,n-i))这里，每一层递归贡献的复杂度恰好是关键点与边缘的距离，而我们每次都找最靠近边缘的一个关键点，相当于启发式里面的对较小的部分进行操作的思想一样。
然后就做完了，这种两端向中间枚举的思想很值得学习和思考。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=200005;
int n,a[N];
int dizlis[N],dizcnt;
int pre[N],nex[N],mark[N];
void Diz(){
dizcnt=n;
memcpy(dizlis,a,(dizcnt+1)*sizeof(int));
sort(dizlis+1,dizlis+1+dizcnt);
dizcnt=unique(dizlis+1,dizlis+1+dizcnt)-dizlis-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(dizlis+1,dizlis+1+dizcnt,a[i])-dizlis;
}
bool check(int l,int r){
if(l>r) return true;
int p1=l,p2=r;
while(p1<=p2){
if(pre[p1]<l&&nex[p1]>r)
return check(l,p1-1)&&check(p1+1,r);
p1++;
if(pre[p2]<l&&nex[p2]>r)
return check(l,p2-1)&&check(p2+1,r);
p2--;
}
return false;
}
int Main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
Diz();
for(int i=1;i<=dizcnt;i++) mark[i]=0;
for(int i=1;i<=n;i++)
pre[i]=mark[a[i]],mark[a[i]]=i;
for(int i=1;i<=dizcnt;i++) mark[i]=n+1;
for(int i=n;i>=1;i--)
nex[i]=mark[a[i]],mark[a[i]]=i;
puts(check(1,n)?"non-boring":"boring");
return 0;
}
int main(){
int T;
scanf("%d",&T);
while(T--) Main();
return 0;
}