[Codeforces Round #779 (Div. 2)] C. Shinju and the Lost Permutation

 

---

★n을 받으면 1~n까지의 수열이 생긴다. 중복은 존재하지 않는다.

※ 1은 무조건 하나여야 한다.

(1은 가장 큰 수가 맨 앞에 들어 오는 것이다. 1이 없거나, 두 개 이상이면 ★을 만족하지 않는다)

 

※ 순열(i+1) - i 의 차이는 무조건 1이하다.

(전의 수 > 현재 수 -> 전의 수가 현재 수 뒤로 가기 때문에 현재 수 + (전의 수 개수) 가 된다.) (전의 수 개수 + 1)

[4,1,2,6,5,3] = 2 -> [3,4,1,2,6,5] = 3

(전의 수 < 현재 수 -> 현재 수가 더 크기 때문에 (전의 수 개수)를 다 덮어 버린다.) (현재 수 + 전의 수 보다 큰 수 개수)

[4,1,2,3,6,5] = 2 -> [5,4,1,2,3,6] = 2

 

※순열 i가 n과 같다면 i+1은 무조건 1이다.

(n == 6 이라면 오직 [1,2,3,4,5,6]밖에 없다. 이 다음은 [6,1,2,3,4,5]이기 때문에 무조건 1이다)

 

※ 순열 첫번째 수와 마지막 수의 차이는 무조건 1 이하다.

첫번째 수(0)와 마지막 수(n-1)는 가능한 순열에서 바로 다음에 있는 수이다.

[(0),x, x, x (n-1)] = [a(0), b(n-1), x, x, x]

a > b 라면 a가 순열의 마지막에 올 때 b가 a를 덮어버린다. 이 b의 개수는 무조건 a개수보다 작다.

a개수가 3이였다면 a(== 1) + b의 개수(==2) 였기 때문에 a가 마지막에 오면 b개수만 남는다.

이 수는 무조건 a개수보다 1작은 수다. a만 빠졌기 때문

a < b 라면 a를 덮어버린다.

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			int n = Integer.parseInt(br.readLine());
 			int[] arr = new int[n];
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 			int count = 0;
 			for(int i = 0; i < n; i++) {
 				arr[i] = Integer.parseInt(st.nextToken());
 				if(arr[i] == 1) {
 					count++;
 				}
 			}
 			boolean result = true;
 			for(int i = 0; i < n-1; i++) {
 				
 				if(arr[i+1]-arr[i] > 1) {
 					result = false;
 					break;
 				}
 				if(arr[i] == n && arr[i+1] != 1) {
 					result = false;
 					break;
 				}
 			}
 			if(arr[0]-arr[n-1] > 1) {
 				result = false;
 			}
 			
 			if(result && count == 1) {
 				sb.append("YES").append('\n');
 			}
 			else {
 				sb.append("NO").append('\n');
 			}
 		}
 		System.out.println(sb);
  	}
}