25287번 - 순열 정렬

$1$부터 $N$까지의 정수를 임의로 배열한 순열은 총 $N! = N\times(N-1)\times(N-2)\times\cdots\times1$가지가 있다. 예를 들어 $1$부터 $3$까지의 수를 임의로 배열한 순열은 $\lbrace1,2,3\rbrace, \lbrace1,3,2\rbrace, \lbrace2,1,3\rbrace, \lbrace2,3,1\rbrace, \lbrace3,1,2\rbrace, \lbrace3,2,1\rbrace$로 총 6가지가 있다.

다음과 같은 연산을 원하는 만큼 사용해서 수들이 감소하지 않도록 만들려고 한다. 연산을 수행한 결과는 순열이 아니어도 된다.

• $i$를 $N-i+1$로 바꾼다.

예를 들어, 크기가 $N = 5$인 순열 $\lbrace 5,2,3,4,1 \rbrace$이 주어졌다고 하자. 첫 번째 원소를 $1(=N-5+1)$로 바꾸고, 다섯 번째 원소를 $5(=N-1+1)$로 바꾸면 $\lbrace 1,2,3,4,5 \rbrace$가 되어 감소하지 않는 수열을 만들 수 있다.

연산을 아무리 많이 사용해도 감소하지 않도록 만들 수 없는 순열이 존재한다. 순열이 주어지면 감소하지 않도록 만들 수 있는지 판별하는 프로그램을 작성하자.

첫째 줄에 테스트케이스의 개수 $T$가 주어진다. ($1 \leq T \leq 50\,000$)

각 테스트케이스는 두 줄로 구성되어 있다.

테스트케이스의 첫째 줄에 순열의 길이 $N$이 주어진다. $(1 \leq N \leq 50\,000)$

테스트케이스의 둘째 줄에 순열을 의미하는 $N$개의 수가 공백으로 구분되어 주어진다. 순열은 $1$부터 $N$까지의 정수가 한 번씩 등장한다.

모든 테스트케이스에서 $N$의 합은 $50\,000$을 넘지 않는다.

각 테스트케이스마다 주어진 순열을 감소하지 않도록 만들 수 있으면 "YES" , 만들 수 없으면 "NO"를 출력한다.