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 n−1n−1 inclusively, and then sort the prefix of the array of length lenlen and the suffix of the array of length n−lenn−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?
There are several test cases in the input data. The first line contains a single integer tt (1≤t≤1001≤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 (2≤n≤1042≤n≤104) — the length of the array.
The second line of the test case contains a sequence of integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the array elements.
It is guaranteed that the sum of nn over all test cases does not exceed 104104.
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).
3 3 2 2 1 4 3 1 2 1 5 1 2 2 4 4
YES YES NO
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.