codeforces#P1420A. Cubes Sorting
Cubes Sorting
Description
Oh, that's funny, is it? Oh it's funny? Because we've been at this for twelve hours and you haven't solved it either, so I don't know why you're laughing. You've got one hour! Solve it!
Wheatley decided to try to make a test chamber. He made a nice test chamber, but there was only one detail absent — cubes.
For completing the chamber Wheatley needs $n$ cubes. $i$-th cube has a volume $a_i$.
Wheatley has to place cubes in such a way that they would be sorted in a non-decreasing order by their volume. Formally, for each $i>1$, $a_{i-1} \le a_i$ must hold.
To achieve his goal, Wheatley can exchange two neighbouring cubes. It means that for any $i>1$ you can exchange cubes on positions $i-1$ and $i$.
But there is a problem: Wheatley is very impatient. If Wheatley needs more than $\frac{n \cdot (n-1)}{2}-1$ exchange operations, he won't do this boring work.
Wheatly wants to know: can cubes be sorted under this conditions?
Each test contains multiple test cases.
The first line contains one positive integer $t$ ($1 \le t \le 1000$), denoting the number of test cases. Description of the test cases follows.
The first line of each test case contains one positive integer $n$ ($2 \le n \le 5 \cdot 10^4$) — number of cubes.
The second line contains $n$ positive integers $a_i$ ($1 \le a_i \le 10^9$) — volumes of cubes.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
For each test case, print a word in a single line: "YES" (without quotation marks) if the cubes can be sorted and "NO" (without quotation marks) otherwise.
Input
Each test contains multiple test cases.
The first line contains one positive integer $t$ ($1 \le t \le 1000$), denoting the number of test cases. Description of the test cases follows.
The first line of each test case contains one positive integer $n$ ($2 \le n \le 5 \cdot 10^4$) — number of cubes.
The second line contains $n$ positive integers $a_i$ ($1 \le a_i \le 10^9$) — volumes of cubes.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
Output
For each test case, print a word in a single line: "YES" (without quotation marks) if the cubes can be sorted and "NO" (without quotation marks) otherwise.
Samples
3
5
5 3 2 1 4
6
2 2 2 2 2 2
2
2 1
YES
YES
NO
Note
In the first test case it is possible to sort all the cubes in $7$ exchanges.
In the second test case the cubes are already sorted.
In the third test case we can make $0$ exchanges, but the cubes are not sorted yet, so the answer is "NO".