Sorting Parts solution codeforces

Sorting Parts solution codeforces

SOLUTION:- CLICK HERE

You have an array aa of length nn. You can exactly once select an integer lenlen between 11 and n1n−1 inclusively, and then sort the prefix of the array of length lenlen and the suffix of the array of length nlenn−len independently.

For example, if the array is a=[3,1,4,5,2]a=[3,1,4,5,2], and you choose len=2len=2, then after that the array will be equal to [1,3,2,4,5][1,3,2,4,5].

Could it be that after performing this operation, the array will not be sorted?

Input

There are several test cases in the input data. The first line contains a single integer tt (1t1001≤t≤100) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer nn (2n1042≤n≤104) — the length of the array.

The second line of the test case contains a sequence of integers a1,a2,,ana1,a2,…,an (1ai1091≤ai≤109) — the array elements.

It is guaranteed that the sum of nn over all test cases does not exceed 104104.

Output

For each test case of input data, output “YES” (without quotes), if the array may be not sorted, output “NO” (without quotes) otherwise. You can output each letter in any case (uppercase or lowercase).

Example
input

Copy
3
3
2 2 1
4
3 1 2 1
5
1 2 2 4 4
output

Copy
YES
YES
NO
Note

In the first test case, it’s possible to select len=1len=1, then after operation, the array will not be sorted and will be equal to [2,1,2][2,1,2].

In the second test case, it’s possible to select len=3len=3, then after operation, the array will not be sorted and will be equal to [1,2,3,1][1,2,3,1].

In the third test case, the array will be sorted for every possible lenlen.

SOLUTION:- CLICK HERE

Leave a Comment

Your email address will not be published.