Non-boring Sequences

Time limit5sMemory limit128 MB

Summary

Determine whether every contiguous subarray of a sequence has at least one element unique within that subarray, using an efficient divide and conquer approach.

Level: Medium7 of 10
Topics: Divide and conquer, Array, Recursion
Solved: No attempts yet

Problem

We were worried this statement might get too boring, so we kept it short.

A sequence is called non-boring if every one of its contiguous subsequences contains at least one unique element — an element whose value appears nowhere else in that subsequence.

Given a sequence of integers, decide whether it is non-boring.

Input

The first line contains the number of test cases $T$ . The test cases follow.

The first line of each test case contains the length of the sequence $n$ ( $1 \le n \le 200\,000$ ). The next line contains the $n$ elements of the sequence, separated by single spaces. Every element is a non-negative integer less than $10^9$ .

Output

For each test case, print the answers in the order the test cases appear in the input. For each test case, print a single line containing either non-boring or boring.

Examples5

Example 1

Input

Expected output

non-boring
boring
non-boring
boring

Example 2
Input
```
1
1
0
```
Expected output
```
non-boring
```
Example 3
Input
```
1
2
999999999 999999999
```
Expected output
```
boring
```
Example 4
Input
```
1
7
4 2 3 1 3 2 4
```
Expected output
```
non-boring
```

Example 5

Input

Expected output

boring
boring
non-boring