Maximum Number of Moves with Same Result

Each operation removes the first two elements, the last two elements, or the first and last elements. The sum of the two removed numbers must be the same in every operation. Find the maximum number of operations. No operation is possible when fewer than 2 elements remain.

输入格式

The first line contains N (1..1000), and the second line contains N positive integers (1..10⁹).

输出格式

Output a single integer, the answer.

样例 1

输入：

7
3 1 5 3 3 4 2

输出：

3

样例 2

输入：

8
4 1 4 3 3 2 5 2

输出：

4

样例 3

输入：

1
1

输出：

0

样例说明

Example 1: first remove 4+2, then the first and last elements 3+3, and finally 1+5; all sum to 6, for 3 operations.

Example 2: remove the first and last elements 4+2, 1+5, 4+2, 3+3 in turn, for 4 operations.

Example 3: a length of 1 allows no removal, so the answer is 0.