난이도:다이아&마스터
문제: 왜곡 정렬

컴돌이는 이상한 정렬 기계를 만들었다.

이 기계는 일반적인 정렬과 달리, 특정한 조건에서만 배열을 뒤집을 수 있다.

길이 N의 순열 P가 주어질 때,
다음 연산을 원하는 만큼 수행할 수 있다.

연산

두 위치 l, r (1 ≤ l < r ≤ N)을 선택한다.

단, 아래 조건을 만족해야 한다.

 
P_l 와 P_r 의 홀짝성이 서로 달라야 한다.

즉,

  • 하나는 홀수
  • 다른 하나는 짝수

여야 한다.

조건을 만족하면 구간 [l, r]을 뒤집을 수 있다.

즉,

 
P_l, P_{l+1}, ..., P_r

를

 
P_r, P_{r-1}, ..., P_l

로 바꾼다.

수열을 오름차순으로 만들 수 있는지 판별하시오.

입력

첫째 줄에 정수 N이 주어진다.

둘째 줄에 1부터 N까지가 한 번씩 등장하는 순열 P가 주어진다.

출력

수열을 오름차순으로 만들 수 있으면 YES,
불가능하면 NO를 출력한다.

제한

  • 1 ≤ N ≤ 200000

예제 입력 1

 
4
1 2 3 4

예제 출력 1

 
YES

예제 입력 2

 
4
2 1 4 3

예제 출력 2

 
YES

예제 입력 3

 
5
1 3 2 5 4

예제 출력 3

 
YES