408858: GYM103351 H Median

Marco is an expert in data structures. He is so good in those kind of problems that he is able to tell the solution to the problem before even reading it to the end. The other day he was the only one to solve a '3D persistent segment tree' tagged problem.

Vitya, however, doubts Marco's skills. He recently came up with a problem Marco could not solve from the first glance! The problem itself is described below.

You are given a permutation $$$p_1, \ldots, p_n$$$. For each $$$1 \le x \le n$$$ you have to determine if there exists a segment $$$1 \le l \le r \le n$$$ of odd length bigger than $$$1$$$ such that the median of $$$(p_l, \ldots, p_r)$$$ is exactly $$$x$$$.

Marco is very confused. Where are the queries and updates? Why is it asking for a median nonsense instead of a very logical and realistic segment sum? These are the questions Marco will probably never know the answer to. The only question remains — how to solve this problem?

The first line contains a single integer $$$T$$$ — the number of test cases. Each test case contains two lines of input ($$$1 \le T \le 100000$$$).

First line of each test case contains a single integer $$$n$$$ — the size of the permutation $$$p$$$ ($$$3 \le n \le 300000$$$).

Second line of each test case contains exactly $$$n$$$ space-separated integers $$$p_1, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i \neq p_j$$$ if $$$i \neq j$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300000$$$.

For each test case output a string $$$s$$$ of length exactly $$$n$$$. If the answer for $$$x$$$ is true, $$$s_x$$$ should be equal to 'y'. Otherwise, $$$s_x$$$ should be equal to 'n'.

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

nyynn
nyn
nyyyn