Problem Description

Given $n$ integers arranged in a circle, two players take numbers according to the following rules:

• The player who takes first may take any number.
• The player who takes second may only take one of the two numbers adjacent (left or right) to the number taken in the previous move.
• The player who takes third may take one of the two numbers adjacent (left or right) to any number that has been taken before.

Here, the first number and the $n$-th number are adjacent to only one number.

The two players take turns. After all numbers have been taken, the player who has taken more odd numbers wins.

Find how many different opening moves the first player has such that they can win the game.

Input Format

The first line contains an integer $n$, the number of integers.

The second line contains $n$ integers, the values of the numbers.

Output Format

Output one integer on one line, the number of opening moves with which the first player wins the game.

3
3 1 5

3

4
1 2 3 4

2

8
4 10 5 2 9 8 1 7

5

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 100$, and each input number is between $1$ and $1000$.

Notes

This problem is translated from COCI2006-2007 CONTEST #5 T5 IVANA.

Translated by ChatGPT 5