34728번 - 스왑 스왑

문제

길이 $N$인 순열(1부터 $N$까지의 모든 정수가 정확히 한 번씩 등장하는 수열) $a_1, a_2, \dots, a_N$이 주어진다. 다음 연산을 원하는 만큼(0회 이상) 적용하여 수열을 오름차순으로 만들 수 있는지 판별하라.

한 번의 연산은 아래 두 동작을 이 순서로 "모두" 수행하는 것이다.

1. 임의의 $i$를 골라 위치 $i$와 $i+1$의 원소를 교환한다. $(1 \le i \le N-1)$
2. 임의의 $j$를 골라 위치 $j$와 $j+2$의 원소를 교환한다. $(1 \le j \le N-2)$

각 연산마다 $i$와 $j$는 자유롭게 선택할 수 있으며, $i=j$를 선택하는 것도 허용된다.

연산을 통해 수열을 오름차순으로 만들 수 있다면 Yes를 출력하고, 그렇지 못한다면 No를 출력하라.

입력

첫째 줄에 정수 $N(3 \le N \le 2,000)$이 주어진다.

둘째 줄에 순열 $a_1, a_2, \dots, a_N$이 주어진다.

수열은 1부터 N까지의 숫자가 정확히 1번 등장한다.

출력

주어진 순열을 위의 연산들로 오름차순으로 만들 수 있으면 Yes, 그렇지 않으면 No를 출력한다.

제한

노트