Migrated from Lutece 2931 The Crazy Ones

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

本题解法:分治(启发式)/扫描线

Here’s to the crazy ones.
The misfits.
The rebels.
The troublemakers.
The round pegs in the square holes.
The ones who see things differently.
They’re not fond of rules.
And they have no respect for the status quo.
You can quote them, disagree with them, glorify or vilify them.
About the only thing you can’t do is ignore them.
Because they change things. They push the human race forward.
And while some may see them as the crazy ones, we see genius.
Because the people who are crazy enough to think they can change the world
are the ones who do.

现在，我们有一个长度为 $n$ 的序列 $a$。

若存在 $1\le i \le n$ ,使 $\forall1\le j \le n$ 且 $j \neq i$,都有 $a_i \neq a_j$ ,则称$a_i$ 为序列 $a$ 的crazy ones。 进一步地，如果任意 $1\le l \lt r \le n$, 序列$a_l, a_{l+1}, \cdots, a_r$ 都存在crazy ones, 则称序列 $a$ 是crazy的。

对于给定的序列，判断它是否是crazy的，如果是输出crazy,否则输出non-crazy。

Input

第一行一个整数 $T$ ，表示数据组数。 此后每组数据,第一行一个整数 $n$ ，为序列长度；第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$，为给出的序列。

Output

Samples

3
6
1 1 4 5 1 4
7
1 9 1 9 8 1 0
10
1 4 5 1 4 1 9 8 1 0

non-crazy
non-crazy
crazy

Constraints

$1 \le n \le 2 \times 10^5, 0 \le a_i \le 10^9, \sum n \le 2 \times 10^6$

Resources

2023 UESTC ICPC Training for Data Structures