题目描述

给定一个长度为 $n$ 的排列 $p = [p_1, p_2, \dots p_n]$，对于所有的整数 $x$ 满足 $1 \leq x \leq n$，你要确定：是否存在一个长度为奇数且不为 $1$ 的区间 $[l, r]$，使得 $x$ 是 $p_l, p_{l + 1}, \dots p_{r - 1}, p_r$ 的中位数。

输入格式

本题单个测试点内有多组测试数据。第一行是一个整数 $T$，表示数据组数。对每组数据，按如下格式读入：

第一行是一个整数，表示排列的长度 $n$。
第二行是 $n$ 个整数，表示这个排列 $p$。

输出格式

对于每组数据，输出一行一个长度为 $n$ 的字符串。如果对 $x$ 存在符合要求的区间，则 $s$ 的第 $x$ 个字符是 $\mathrm{y}$，否则 $s$ 的第 $x$ 个字符是 $\mathrm{n}$。

样例

样例输入 1

3
5
5 1 3 2 4
3
2 3 1
5
1 2 3 4 5

样例输出 1

nyynn
nyn
nyyyn

输入输出样例 2

见选手目录下的 /medium/medium2.in 和 /medium/medium2.ans。

输入输出样例 3

见选手目录下的 /medium/medium3.in 和 /medium/medium3.ans。

这个样例满足特殊性质 B。

输入输出样例 4

见选手目录下的 /medium/medium4.in 和 /medium/medium4.ans。

这个样例满足特殊性质 C。

数据范围与提示

我们用 $N$ 表示单个测试点内 $n$ 之和，则数据范围满足如下约定：

• 特殊性质 A：$n \leq 8$。
• 特殊性质 B：对每组数据，至多存在 $100$ 个 $i \in [2, n-1]$，满足 $(p_{i} - p_{i - 1})(p_{i + 1} - p_{i}) < 0$。
• 特殊性质 C：测试点内的全部数据总共存在至多 $4000$ 个 $i \in [2, n-1]$，满足 $(p_{i} - p_{i - 1})(p_{i + 1} - p_{i}) < 0$。

对于全部的测试数据，保证 $1 \leq T \leq 120$，$3 \leq n \leq N \leq 10^6$，输入的 $p_i$ 是一个排列。