홀짝 수열

문제

홀짝 수열이란 다음 조건을 만족 시키는 정수 수열이다.

• 수열의 홀수번째 원소는 모두 홀수여야 하고, 순서대로 나열했을 때 감소하지 않아야 한다.

• 수열의 짝수번째 원소는 모두 짝수여야 하고, 순서대로 나열했을 때 감소하지 않아야 한다.

다음과 같은 수열은 홀짝 수열이다 $[1, 2, 1], [3], [5, 4]$

그러나 다음과 같은 수열은 홀짝 수열이 아니다. $[3, 2, 1], [2, 2], [5, 4, 7, 2]$

$[3, 2, 1]$의 홀수번째 원소들을 순서대로 나열하면 $[3, 1]$인데, 감소하기 때문에 홀짝 수열이 아니다.

$[2, 2]$는 첫 번째 원소가 홀수가 아니므로 홀짝 수열이 아니다.

$[5,4,7,2]$의 짝수번째 원소들을 순서대로 나열하면 $[4, 2]$인데, 감소하기 때문에 홀짝 수열이 아니다.

시온이는 길이 $N$의 수열을 가지고 있다. 이 수열을 잘 정렬한다면 홀짝 수열로 만드는 것이 가능할까?

입력

첫째 줄에 수열의 길이 $N(1\le N \le 100)$이 주어진다.

둘째 줄에 수열의 원소가 주어진다. 수열의 $i$번째 원소는 정수 $a_i(1\le a_i \le 100)$이다.

출력

주어진 수열을 잘 정렬해서 홀짝 수열로 만들 수 있다면 1 을, 어떻게 정렬하더라도 홀짝 수열로 만들 수 없다면 0 을 출력한다.

예제 입력 1

3
2 1 1

예제 출력 1

1

예제 입력 2

3
4 2 3

예제 출력 2

0

예제 입력 3

5
4 1 6 3 5

예제 출력 3

1