Problem Description

Translated from COI 2021 T2 "Cigle"

You are a designer, and you are currently pondering your next design.

You can use $N$ bricks, each with a length of $d_i$ and a width of one unit, to build a multi-row brick wall, where each row is one unit long. The construction method is as follows:

• Start by placing bricks from left to right in the first row, which is the bottom row.
• Next, in the second row, which is above the first row, place bricks from right to left, aligning the right edge of the middle row's rightmost brick with the right edge of the bottom row's rightmost brick.
• Then, in the third row, place the remaining bricks from left to right, aligning the left edge of the middle row's leftmost brick with the left edge of the top row's leftmost brick.
• Continue this pattern alternately.

Since the bricks are magical, they can float in the air.

The beauty of a brick wall is defined as the number of vertices that are shared by four bricks.

Given the lengths of each brick in the order they are placed, find the maximum beauty.

Input Format

The first line contains an integer $N$.

The next line contains $N$ integers $d_i$.

Output Format

Output a single integer, which represents the maximum beauty.

Sample Input and Output

Sample Input #1

6
2 2 2 1 1 2

Sample Output #1

2

Sample Input #2

13
9 5 2 8 8 2 5 9 9 7 8 5 10

Sample Output #2

5

Sample Input #3

12
5 5 2 3 2 1 1 5 5 2 5 1

Sample Output #3

4

Notes

Sample Explanation

Sample #3 Explanation:

Data Range

For all data, $1 \le N, d_i \le 5 \times 10^3$.

见题面 Input 部分

见题面 Output 部分