[Solution] Sorting Parts solution codeforces

Sorting Parts solution codeforces – You have an array 𝑎a of length 𝑛n. You can exactly once select an integer 𝑙𝑒𝑛len between 11 and 𝑛1n−1 inclusively, and then sort the prefix of the array of length 𝑙𝑒𝑛len and the suffix of the array of length 𝑛𝑙𝑒𝑛n−len independently.

For example, if the array is 𝑎=[3,1,4,5,2]a=[3,1,4,5,2], and you choose 𝑙𝑒𝑛=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?

Sorting Parts solution codeforces

There are several test cases in the input data. The first line contains a single integer 𝑡t (1𝑡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 𝑛n (2𝑛1042≤n≤104) — the length of the array.

The second line of the test case contains a sequence of integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109) — the array elements.

It is guaranteed that the sum of 𝑛n 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).

Sorting Parts solution codeforces

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


Sorting Parts solution codeforces Note

In the first test case, it’s possible to select 𝑙𝑒𝑛=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 𝑙𝑒𝑛=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 𝑙𝑒𝑛len.

Leave a Comment