9078번 - 정렬

주어진 숫자 열을 정렬하는데, 사용할 수 있는 연산은 이웃하는 두 숫자를 다른 두 수 사이나 숫자열의 맨 앞 혹은 맨 뒤에 끼워 넣는 것 뿐이다. 즉, 한 번에 숫자를 하나씩 옮기는 것이 아니라, 이웃하는 숫자를 두 개씩 묶어서 옮긴다. 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의 정수로 구성된 숫자 열이 주어졌을 때, 그것이 위의 연산만으로 정렬가능한지 여부를 결정하는 프로그램을 작성하시오.

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 정수 N(1 ≤ N ≤ 100)이 주어지고, 둘째 줄에는 N개의 정수가 공백을 사이에 두고 주어진다.

각 테스트 케이스에 대해서 정렬 가능하면 YES를, 아니면 NO를 한 줄에 하나씩 출력한다.