Winning Opening Moves in the Circular Picking Game

Given n integers arranged in a line, two players play a game by taking turns to pick numbers according to the following rules:

1. The first player may choose any number as the opening move.
2. The second player must choose one of the two numbers adjacent to the number just taken. (Note: the first and the last elements in the line have only one adjacent number.)
3. From the third move onward, the current player may pick any number that is adjacent to any number that has already been taken.

After all the numbers have been picked, the player who has collected more odd numbers wins the game.

Your task is to determine the number of different opening moves (i.e. the first move choices) for the first player that guarantee a win under optimal play from both sides.

All formulas are in LaTeX format. In particular, if we denote by \( v_i = 1 \) when the \( i^{th} \) number is odd and \( 0 \) otherwise, and define a function \( dp(l, r) \) for a contiguous segment via:

\[ dp(l,r) = \max\bigl\{ v_l - dp(l+1, r),\; v_r - dp(l, r-1) \bigr\} \]

(with \( dp(l, r) = 0 \) when \( l > r \)), then if the first player picks the \( i^{th} \) number, the remaining game splits into two segments: \([1, i-1]\) and \([i+1, n]\). The overall winning condition for that opening move is:

\[ v_i - \Bigl(dp(1, i-1) + dp(i+1, n)\Bigr) > 0 \]

Count the number of indices \( i \) (with \( 1 \le i \le n \)) for which the above inequality holds.

inputFormat

The input consists of two lines:

• The first line contains an integer \( n \) (\(1 \le n \le 1000\)), representing the number of integers.
• The second line contains \( n \) space-separated integers.

outputFormat

Output a single integer representing the number of winning opening moves for the first player.

sample

1
3

1