Split into Odd or Split into Even!

Interview

Time limit1sMemory limit1024 MB

Summary

Given a sequence of positive integers, decide whether it can be split into an odd number of sets with odd sums, or an even number of sets with even sums.

Level: Easy3 of 10
Topics: Math, Array
Solved: No attempts yet

Problem

Given a sequence $A$ of length $N$ made of positive integers, you must split the sequence into one or more sets by grouping consecutive elements. When splitting, you may choose one of two methods: split into odd or split into even. Every element of the sequence must belong to exactly one of the sets.

Split into odd
- The sum of the elements in each set must be odd.
- The sequence must be split into an odd number of sets.
Split into even
- The sum of the elements in each set must be even.
- The sequence must be split into an even number of sets.

Determine whether the sequence can be split into one or more sets using one of these methods.

Input

The first line contains the length $N$ of the sequence $A$ . $1\leq N\leq 200,000$

The second line contains the elements $A_i$ of the sequence, separated by spaces. $1\leq A_i\leq 10^9$

Output

If the sequence can be split into one or more sets using one of the given methods, print 1. Otherwise, print 0.

Hint

The input is large, so use fast I/O. Examples for common languages are below.

C++: When using cin and cout, call cin.tie(nullptr); ios::sync_with_stdio(false); once before any input or output. Use '\n' instead of endl for line breaks.
Java: Use BufferedReader and BufferedWriter.
Python3, PyPy3: Use sys.stdin.readline().rstrip() instead of input().

Examples3

Example 1
Input
```
5
1 2 1 2 1
```
Expected output
```
1
```
Example 2
Input
```
6
1 2 4 4 2 1
```
Expected output
```
0
```
Example 3
Input
```
7
1 2 4 3 2 2 2
```
Expected output
```
1
```