#1166 정렬

11  1 s   128 MB  

Description

주어진 숫자 열을 정렬하는데, 사용할 수 있는 연산은 이웃하는 두 숫자를 다른 두 수 사이나 숫자열의 맨 앞 혹은 맨 뒤에 끼워 넣는 것뿐이다. 즉, 한 번에 숫자를 하나씩 옮기는 것이 아니라, 이웃하는 숫자를 두 개씩 묶어서 옮긴다. 4 1 5 3 2 의 경우 다음과 같이 정렬할 수 있다.

4 1 5 3 2  3 2 4 1 5  3 4 1 2 5  1 2 3 4 5

그러나 2 1 3 의 경우에는 어떻게 하더라도 정렬할 수 없다.

이와 같이 입력으로 1에서 N 까지의 서로 다른 N 개의 정수들로 구성된 숫자 열이 주어질 때 그것이 위의 연산만으로 정렬가능한지 여부를 결정하는 프로그램을 작성하시오.

Input

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스로는 두 줄로 이루어진다. 첫 번째 줄은 정수 N (1 ≤ N ≤ 100)이 주어지고, 두 번째 줄은 N 개의 정수들이 공백을 사이에 두고 주어진다.

Output

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 정렬 가능하면 YES를, 아니면 NO를 한 줄에 하나씩 출력하시오.

Sample Input

Sample Output

3
3
1 2 3
4
2 4 1 3
7
3 6 7 1 2 4 5
YES
NO
YES