KVAR - Kevin likes array

Kevin likes array. This time he has a array A[1], A[2] ... A[N]. He calls a array beautiful, if the number of inversions is equal to the number of its local inversions. The number of inversion is equal to the number of pairs (i;j) such that 1 ≤ i ≤ j ≤ N and A[i] > A[j] and number of its local inversions is the number of integers i such that 1 ≤ i < N and A[i] > A[i+1]. So help him to find whether the array is beautiful or not. Print YES for a corresponding test case if it is beautiful and NO otherwise.

Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 100

1 ≤ A[i] ≤ 100

Example

Input:
4
1
1
2
2 1
3
3 2 1
4
1 3 2 4

Output:
YES
YES
NO
YES

Explanation

Case 1.Here N = 1, so we have no pairs (i; j) with 1 ≤ i < j ≤ N. So the number of inversions is equal to zero. The number of local inversion is also equal to zero. Hence this array is beautiful.

Case 2. Here N = 2, and we have one pair (i; j) with 1 ≤ i < j ≤ N, the pair (1; 2). Since A[1] = 2 and A[2] = 1 then A[1] > A[2] and the number of inversions is equal to 1. The number of local inversion is also equal to 1 since we have one value of i for which 1 ≤ i < N (the value i = 1) and A[i] > A[i+1] for this value of i since A[1] > A[2]. Hence this permutation is also good.

Case 3. Here N = 3, and we have three pairs (i; j) with 1 ≤ i < j ≤ N. We have A[1] = 3, A[2] = 2, A[3] = 1. Hence A[1] > A[2], A[1] > A[3] and A[2] > A[3]. So the number of inversions is equal to 3. To count the number of local inversion we should examine inequalities A[1] > A[2] and A[2] > A[3]. They both are satisfied in our case, so we have 2 local inversions. Since 2 ≠ 3 this array is not beautiful.

Case 4. Here we have only one inversion and it comes from the pair (2; 3) since A[2] = 3 > 2 = A[3]. This pair gives also the only local inversion in this permutation. Hence the number of inversions equals to the number of local inversions and equals to one. So this array is beautiful


Added by:Samar
Date:2021-06-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.