#84 Parity Sort

Loading problem...

Preparing the statement, recent submissions, and submit form.

Statement

길이 $N$ 의 정수 수열 $A$ 가 주어진다. 다음 연산을 원하는 만큼 수행할 수 있다.

수열의 인덱스는 $1$ 부터 시작한다. 주어진 연산만을 사용하여 수열을 오름차순, 즉 비내림차순으로 정렬할 수 있는지 판별하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

주어진 연산만을 사용하여 수열을 오름차순으로 정렬할 수 있으면 YES, 아니면 NO를 출력한다.

Sample 1

Input

3
1 1 1

Output

YES

이미 비내림차순으로 정렬되어 있다.

Sample 2

Input

3
2 1 3

Output

정렬된 수열은 $1,2,3$ 이다. 하지만 $1$ 은 짝수 인덱스에 있고, 정렬된 수열에서는 홀수 인덱스에 있어야 한다. 인덱스의 홀짝성은 바꿀 수 없으므로 정렬할 수 없다.

Sample 3

Input

4
3 4 1 2

Output

YES

$1$ 번 인덱스와 $3$ 번 인덱스를 교환하고, $2$ 번 인덱스와 $4$ 번 인덱스를 교환하면 수열은 $1,2,3,4$ 가 된다.