홀수로 나눠라! 짝수로 나눠라!

양의 정수로 이루어진 길이 $N$의 수열 $A$가 주어졌을 때, 연속된 원소들을 묶어 수열을 한 개 이상의 집합으로 나누어야 한다. 집합을 나눌 때는 홀수로 나누기 혹은 짝수로 나누기 중 하나의 방법을 선택할 수 있다. 또한, 수열의 모든 원소는 나눈 집합 중 정확히 하나에 속해야 한다.

• 홀수로 나누기

  • 각 집합을 이루는 원소의 합은 홀수여야 한다.
  • 수열을 홀수 개의 집합으로 나누어야 한다.

• 짝수로 나누기

  • 각 집합을 이루는 원소의 합은 짝수여야 한다.
  • 수열을 짝수 개의 집합으로 나누어야 한다.

둘 중 하나의 방법을 선택하여 주어진 수열을 한 개 이상의 집합으로 나눌 수 있는지를 판별해 보자.

첫째 줄에 수열 $A$의 길이 $N$이 주어진다. $\left(1\leq N\leq 200,000\right)$

둘째 줄에 수열의 원소 $A_i$가 공백으로 구분되어 주어진다. $\left(1\leq A_i\leq 10^9\right)$

주어진 방법 중 하나를 선택하여 수열을 한 개 이상의 집합으로 나눌 수 있다면 1, 아니라면 0을 출력한다.

입출력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 대표적인 언어에 따른 빠른 입출력은 아래를 참고하세요.

• C++: cin, cout을 사용하는 경우 입출력 전에 cin.tie(nullptr); ios::sync_with_stdio(false);를 한 번 적용해야 합니다. 줄 바꿈할 때는 endl 대신 ‘\n’을 사용해야 합니다.
• Java: BufferedReader와 BufferedWriter를 사용해야 합니다.
• Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해야 합니다.