Problem Description

Given \( n \) integers arranged in a circle, two players follow the following rules to take numbers:

• The first player can take any number.
• The second player can only take one of the two adjacent numbers to the last taken number.
• The third player can take one of the two adjacent numbers to any previously taken number.

Note that the first and the \( n \)-th number have only one adjacent number.

The players take turns to take numbers. After all numbers are taken, the player who has taken more odd numbers wins.

Determine how many different starting moves the first player has to ensure a win.

Input Format

The first line contains an integer \( n \), representing the number of digits.

The second line contains \( n \) numbers, representing the specific digits.

Output Format

Output a single integer, representing the number of starting moves that allow the first player to win.

Sample Input and Output

Sample Input #1

3
3 1 5

Sample Output #1

3

Sample Input #2

4
1 2 3 4

Sample Output #2

2

Sample Input #3

8
4 10 5 2 9 8 1 7

Sample Output #3

5

Notes

Data Size and Constraints

For \( 100\% \) of the data, it is guaranteed that \( 1 \le n \le 100 \) and the input numbers are between \( 1 \) and \( 1000 \).

Notes

Translated from COCI2006-2007 CONTEST #5 T5 IVANA.

见题面 Input 部分

见题面 Output 部分