Brick Wall Beauty

This problem is adapted from COI 2021 T2 "Cigle".

You are a designer planning your next design. You have N bricks; the i-th brick has length \(d_i\) and a fixed width of 1 unit. You wish to build a multi‐row brick wall. Each row has a height of 1 unit. The bricks are placed one row at a time using the following procedure:

1. Start with the bottom (first) row. Place some consecutive bricks (in the given order) from left to right.
2. For the second row (immediately above the first row), place some bricks (in order) from right to left so that the rightmost brick of the second row is aligned at its right edge with the rightmost brick of the first row.
3. Then, for the third row, place the next bricks from left to right so that the leftmost brick of the third row is aligned at its left edge with the leftmost brick of the second row.
4. Continue alternating the placement direction for subsequent rows. (For even‐numbered rows the bricks are placed right to left, and for odd‐numbered rows left to right.)

The bricks are magical – they may float in mid‐air so that the rows need not be directly supported below. For any constructed wall the beauty is defined as the number of vertices that are shared by exactly four bricks (i.e. the internal crossing points where a vertical joint in one row exactly meets a vertical joint in the row above).

More precisely, every row has brick boundaries. For a row placed from left to right the internal boundaries are at positions (relative to its left edge) equal to the proper prefix sums of its brick lengths; for a row placed right to left the boundaries occur at positions equal to (total row length minus a proper prefix sum). When two consecutive rows are built according to the rules above they share a common horizontal span, and a vertex (an intersection point of two vertical boundaries, one from each row) will be formed if a boundary (other than the endpoints of the row) of the lower row and a boundary (other than the endpoints) of the upper row coincide. In other words, if the lower row (say, row S) has total length \(S\) and proper boundary positions \(p\) (with \(0 < p S-T\) must hold so that the corresponding boundary in the upper row lies strictly inside that row.)

Your task is: given the bricks in order (i.e. the sequence \(d_1,d_2,\dots,d_N\)) and knowing that you may choose arbitrarily many rows (each row being a contiguous segment of the brick sequence, with at least one brick per row), compute the maximum possible beauty of the wall you can construct.

Note: When a wall consists of only one row, its beauty is 0.

Formulas in \(\LaTeX\) format:

• Total length of a row: \(S = \sum d_i\).
• Proper prefix sums for a row (placed left to right): \(P = \{d_1,\; d_1+d_2,\; \dots,\; S-d_k\}\) (excluding 0 and \(S\)).
• For a row placed right to left, the effective boundaries are \(\{S-d_1,\; S-d_1-d_2,\; \dots,\; d_k\}\).
• If the lower row (with total \(S\) and boundaries \(p\)) is immediately below an upper row (with total \(T\) and boundaries \(q\) in its effective order), then a vertex is formed at a common boundary if and only if there exists \(p\) such that
  \(p > S - T\) and \(S - p \in \{q\}\).

inputFormat

The first line contains an integer \(N\) (the number of bricks).
The second line contains \(N\) positive integers \(d_1,d_2,\dots,d_N\) separated by spaces.

outputFormat

Output a single integer – the maximum beauty (i.e. the maximum number of four‐brick vertices) achievable.

sample

1
3

0