홀짝 수열

길이가 $N$인 수열의 $i(1 \le i \le N)$번째 원소를 정수 $a\_i(1\le a\_i \le 100)$라고 하자. 동훈이는 이 수열을 잘 정렬해서 홀짝 수열로 만들고 싶다. 어떤 수열이 홀짝 수열이 되려면 다음 조건을 만족해야 한다.

1. 수열의 홀수번째 원소는 모두 홀수여야 하고, 순서대로 나열했을 때 감소하지 않아야 한다. $a\_1 \le a\_3 \le a\_5 \le a\_7 \le ...$
2. 수열의 짝수번째 원소는 모두 짝수여야 하고, 순서대로 나열했을 때 감소하지 않아야 한다. $a\_2 \le a\_4 \le a\_6 \le a\_8 \le ...$

다음과 같은 수열은 홀짝 수열이다. $\[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$의 수열 $a\_1,a\_2,…a\_N$이 주어졌을 때, 이 수열을 잘 정렬한다면 홀짝 수열로 만드는 것이 가능할까?

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

둘째 줄에 $a\_1, a\_2, ..., a\_N$이 주어진다. 수열의 $i$번째 원소는 정수 $a\_i(1\le a\_i \le 100)$이다.

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