The Little Elephant likes permutations. This time he has a permutation A[1], A[2], ..., A[N] of numbers 1, 2, ...,N.

He calls a permutation A good, if the number of its inversions is equal to the number of its local inversions. The number of inversions is equal to the number of pairs of integers (i; j) such that 1 ≤ i < j ≤ N and A[i] > A[j],
and the number of local inversions is the number of integers i such that 1 ≤ i < N and A[i] > A[i+1].

The Little Elephant has several such permutations. Help him to find for each permutation whether it is good or not. Print YES for a corresponding test case if it is good and NO otherwise.

Input

The first line of the input contains a single integer T, the number of test cases. T test cases follow. The first line of each test case contains a single integer N, the size of a permutation. The next line
contains N space separated integers A[1], A[2], ..., A[N].

Output

For each test case output a single line containing the answer for the corresponding test case. It should beYES if the corresponding permutation is good and NO otherwise.

Constraints

1 ≤ T ≤ 474

1 ≤ N ≤ 100

It is guaranteed that the sequence A[1], A[2], ..., A[N] is a permutation of numbers 1, 2, ..., N.

Example

Input:

4

1

1

2

2 1

3

3 2 1

4

1 3 2 4

Output:

YES

YES

NO

YES

总结一下有下面关系：

全局逆序数 == 起泡排序交换数据的交换次数

本题数据量小，能够使用暴力法计算。

可是这样时间效率是O(N*N)，要想减少到O(nlgn)那么就要使用merger sort。

以下一个类中暴力法和merge sort方法都包含了。

#pragma once

#include <stdio.h>

#include <stdlib.h>

class LittleElephantAndPermutations

{

	int localInverse(const int *A, const int n)

	{

		int ans = 0;

		for (int i = 1; i < n; i++)

		{

			if (A[i-1] > A[i]) ans++;

		}

		return ans;

	}

	int globalInverse(const int *A, const int n)

	{

		int ans = 0;

		for (int i = 0; i < n; i++)

		{

			for (int j = i+1; j < n; j++)

			{

				if (A[i] > A[j]) ans++;

			}

		}

		return ans;

	}

	int *mergeArr(int *left, int L, int *right, int R, int &c)

	{

		int *lr = new int[L+R];

		int i = 0, j = 0, k = 0;

		while (i < L && j < R)

		{

			if (left[i] <= right[j])

			{

				lr[k++] = left[i++];

			}

			else

			{

				lr[k++] = right[j++];

				c += L-i;

			}

		}

		while (i < L)

		{

			lr[k++] = left[i++];

		}

		while (j < R)

		{

			lr[k++] = right[j++];

		}

		return lr;

	}

	int biGlobalInverse(int *&A, const int n)

	{

		if (n <= 1) return 0;

		int mid = (n-1) >> 1;//记得n-1

		int *left = new int[n];

		int *right = new int[n];

		int L = 0, R = 0;

		for ( ; L <= mid; L++)

		{

			left[L] = A[L];

		}

		for (int i = mid+1; i < n; i++, R++)

		{

			right[R] = A[i];

		}

		delete [] A;

		int c1 = biGlobalInverse(left, L);

		int c2 = biGlobalInverse(right, R);

		int c = 0;

		A = mergeArr(left, L, right, R, c);

		delete left;

		delete right;

		return c1+c2+c;

	}

public:

	void run()

	{

		int T = 0, N = 0;

		scanf("%d", &T);

		while (T--)

		{

			scanf("%d", &N);

			int *A = new int[N];

			for (int i = 0; i < N; i++)

			{

				scanf("%d", &A[i]);

			}

			int loc = localInverse(A, N);

			int glo = biGlobalInverse(A, N);

			if (loc == glo) puts("YES");

			else puts("NO");

		}

	}

};

int littleElephantAndPermutations()

{

	LittleElephantAndPermutations le;

	le.run();

	return 0;

}