Problem N: Real Guaduation Photo

Problem N: Real Guaduation Photo

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 9  Solved: 4
[Submit][Status][Web Board]

Description

VCN Research Center will graduate tomorrow. At that time, they will stand in line and take a graduation photo together. We know that there are \(N\) members in the VCN Research Center, and each one’s heights is different from each other, so that we assign each member a tag according to the rank of his or her height in an increasing order, e.g., the \(5\)-th shortest person will be assigned with a tag of \(5\). Now the photographer comes, and all the members have stood in line. However, the photographer suggests that they should stand in line with a height-increasing order from left to right, in other words, each one should have a tag larger than that of anyone standing on his or her left. To adjust the standing positions, each person could swap his or her position with his or her neighbors. As a result, there must exist at least one way by which least number of positions swaps is needed to adjust everyone’s positions to fit the suggestion of the photographer, and we call it the best swap solution. We say two solutions are different when there exists at least one difference on the swap orders of the solutions. Here is the problem, is there only one best swap solution, or multiple different best swap solutions with the same number of swap times?

Input

The first line contains an integer \(T, 1 ≤ T ≤ 10\), indicating the number of test cases.

For each test case, there will be two lines as follows.

The first line contains an integer \(N, 1 ≤ N ≤ 100000\), indicating the number of members.
The second line contains \(N\) integers, \(p_1, p_2, . . . , p_N\), and \(p_i\) is the tag of the \(i\)-th member.
All the tags are integers in range \([1,N]\) and there is no duplication.

Output

For each test case, output a character in one line. If there is only one best swap solution, output "Y"; if there are multiple best swap solutions, output "N" (both without quotation marks).

Sample Input

2
1
1
3
3 2 1

Sample Output

Y
N

HINT

[Submit][Status]