Medal Distribution

After years of warfare, the Qin Emperor finally unified China. To defend his borders against foreign invasion, he decided to station n generals along the frontier. Unfortunately, the generals have grown proud and rebellious—when they heard that they were to be awarded medals, each general i requested to receive a_i medals, all of which must be of different colors. However, if two adjacent generals (note the arrangement is circular, so general 1 and general n are also adjacent) are awarded any medal of the same color, they will feel insulted and rebel.

To buy time before dealing with these unruly generals, the emperor plans to mint medals using as few distinct colors as possible while still satisfying every general’s request and making sure that any two adjacent generals get disjoint sets of medal colors.

Your task is to help the emperor determine the minimum number of colors that need to be minted.

Assignment details:

• General i (0-indexed for explanation) should receive a_i medals (the medals must be distinct for that general).
• For every pair of adjacent generals (i and i+1, and also generals n and 1) their sets of medal colors must not intersect.
• The same color can be used for medals of non‐adjacent generals.

Input Constraints:

• The first line contains an integer n (n ≥ 2) – the number of generals.
• The second line contains n space‐separated integers a₁, a₂, …, a_n (each a_i ≥ 1), where a_i is the number of medals requested by the i-th general.

Note on the structure of an optimal solution:

The generals are arranged in a circle. Thus, if two generals are not adjacent, they can share medal colors. In particular, if the conflict graph induced by the "adjacent" relation is bipartite (which is the case when n is even), one may partition the generals into two groups. All generals in one group can be given their medals from one pool of colors and those in the other group from another pool. In such a case, the minimum number of colors required is:

$$\text{answer} = \max_{i\in X}\;a_i + \max_{j\in Y}\;a_j, $$

where X and Y are the two partitions.

On the other hand, when n is odd, a 2‐coloring is not possible. In fact, the problem becomes more constrained. In the special case when n = 3, every pair is adjacent and the only solution is to use totally disjoint medals for all three generals, i.e.,

$$\text{answer} = a_1 + a_2 + a_3.$$

For odd cases with n ≥ 5, two lower bounds can be derived:

1. For any adjacent pair (i, i+1) (taking indices modulo n), the medals used must be distinct, thus one must have
   $$a_i + a_{i+1} \le C.$$
2. Since each non-adjacent color may be reused, one also gets a lower bound based on the total demand. It turns out that a valid answer is given by taking the maximum of the following two quantities:
   • $$L_1 = \max_{1 \le i \le n} \bigl(a_i + a_{(i \bmod n)+1}\bigr)$$
   • $$L_2 = \left\lceil \frac{a_1+a_2+\cdots+a_n}{2} \right\rceil$$

Thus, the final answer is determined as follows:

• If n = 2: answer = a₁ + a₂.
• If n is even and n ≥ 4: answer = max(a_i for i in odd positions) + max(a_i for i in even positions) (using 1-indexing).
• If n = 3: answer = a₁ + a₂ + a₃.
• If n is odd and n ≥ 5: answer = max(L₁, L₂) where
  • $$L_1 = \max_{1 \le i \le n} \bigl(a_i + a_{(i \bmod n)+1}\bigr)$$
  • $$L_2 = \left\lceil \frac{a_1+a_2+\cdots+a_n}{2} \right\rceil$$

Your program should compute and output the minimum number of medal colors needed.

inputFormat

The first line of input contains a single integer n (n ≥ 2) — the number of generals.

The second line contains n space‐separated integers a₁, a₂, …, aₙ (each aᵢ ≥ 1), where aᵢ is the number of medals requested by the i-th general.

outputFormat

Output a single integer — the minimum number of distinct medal colors that need to be minted.

sample

2
3 4

7