A. Cubes Sorting

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard outputFor god's sake, you're boxes with legs! It is literally your only purpose! Walking onto buttons! How can you not do the one thing you were designed for?

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 nn cubes. ii-th cube has a volume aiai.

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>1i>1, ai−1≤aiai−1≤ai must hold.

To achieve his goal, Wheatley can exchange two neighbouring cubes. It means that for any i>1i>1 you can exchange cubes on positions i−1i−1 and ii.

But there is a problem: Wheatley is very impatient. If Wheatley needs more than n⋅(n−1)2−1n⋅(n−1)2−1 exchange operations, he won't do this boring work.

Wheatly wants to know: can cubes be sorted under this conditions?

Input

Each test contains multiple test cases.

The first line contains one positive integer tt (1≤t≤10001≤t≤1000), denoting the number of test cases. Description of the test cases follows.

The first line of each test case contains one positive integer nn (2≤n≤5⋅1042≤n≤5⋅104) — number of cubes.

The second line contains nn positive integers aiai (1≤ai≤1091≤ai≤109) — volumes of cubes.

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

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.

Example

input

Copy

3 5 5 3 2 1 4 6 2 2 2 2 2 2 2 2 1

output

Copy

YES YES NO

Note

In the first test case it is possible to sort all the cubes in 77 exchanges.

In the second test case the cubes are already sorted.

In the third test case we can make 00 exchanges, but the cubes are not sorted yet, so the answer is "NO".

 

解题说明：此题是一道水题，当出现已经从大到小排序好的情况下才会让排序次数超过预期值。于是遍历数组进行判断即可。

#include <stdio.h> int main() { int tc; scanf("%d", &tc); while (tc--) { long long n, i, det; scanf("%lld", &n); long long a[50005]; for (i = 0; i < n; i++) { scanf("%lld", &a[i]); } det = 0; for (i = 0; i<n - 1; i++) { if (a[i] <= a[i + 1]) { det = 1; break; } } if (!det) { printf("NO\n"); } else { printf("YES\n"); } } return 0; }