부정확한 컴퓨터

부정확한 컴퓨터(IC)는 구조적 결함이 있어 두 정수의 차이가 2 이상일 때만 두 정수를 올바르게 비교한다. 예를 들어 IC는 '4가 2보다 크다'는 항상 올바르게 답하지만, '2가 3보다 크다' 또는 '3이 2보다 크다' 중 어느 쪽으로도 답할 수 있다(이 경우 IC는 둘 중 하나를 임의로 고른다). 두 정수 x와 y에 대해 IC가 'x가 y보다 크다'고 답할 때 'x가 y를 이긴다'고 말한다.

양의 정수 n이 주어질 때, Pn = {1, 2, … , n}을 1부터 n까지의 양의 정수 집합이라 하자. 이제 IC를 사용해 Pn 위에서 더블 라운드 로빈 토너먼트를 진행한다. 더블 라운드 로빈 토너먼트는 다음과 같이 정의된다:

1. 토너먼트는 두 라운드(1라운드와 2라운드)로 구성된다.
2. 각 라운드에서 Pn의 각 원소는 Pn의 다른 모든 원소와 비교된다.

이제 Pn의 각 원소 k에 대해, ri(k)를 토너먼트의 i번째 라운드에서 k가 이긴 횟수라 하자. 또한 '차이 수열' D = d1d2…dn을 각 1 ≤ k ≤ n에 대해 dk = |r1(k) − r2(k)|로 정의한다.

다음은 n = 5일 때의 예시를 보여준다.

위 예시에서 r1(1) = 0, r1(2) = 1, r1(3) = 3, r1(4) = 3, r1(5) = 3이고, r2(1) = 1, r2(2) = 1, r2(3) = 1, r2(4) = 3, r2(5) = 4이다. 따라서 이 예시에서 차이 수열은 D = 1 0 2 0 1이다.

n개의 음이 아닌 정수로 이루어진 수열이 주어질 때, 입력 수열이 Pn의 차이 수열이 될 수 있는지 판별하는 프로그램을 작성하라.

프로그램은 표준 입력에서 읽는다. 입력은 정수 n (3 ≤ n ≤ 1,000,000)이 포함된 한 줄로 시작되며, 여기서 n은 Pn의 크기이다. 다음 줄에는 0과 n 사이의 n개의 정수로 이루어진 수열이 주어지며, 수열의 각 원소는 하나의 공백으로 구분된다.

프로그램은 표준 출력에 쓴다. 정확히 한 줄을 출력한다. 수열이 Pn의 차이 수열이 될 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.