Minimum Number of Players

We are given (n) buildings numbered (1,2,\dots,n). Some competitions have been held according to the following rule. In each competition exactly three players participate. Suppose the three players come from buildings with numbers (a, b, c) (not necessarily distinct). The competition is held in the building with number (\mathrm{median}(a,b,c)) (i.e. the middle value when (a, b, c) are sorted in non‐decreasing order). In particular, if (a=b) then regardless of the value of (c) the competition will be held in building (a).

It is known that every triple of players holds at most one competition, and that for every building (i) the number of competitions held in building (i) is exactly (a_i) (these counts are given as input). However, we do not know how many players are in each building. Your task is to determine the minimum total number of players (placed among the (n) buildings) so that there exists some distribution of players and a selection of competitions (from the available triples of players) that yields the given competition counts.

A key observation is that if players are assigned to buildings with counts (x_1,x_2,\dots,x_n) (and the players in each building are assumed to be consecutive in the overall order from building 1 to (n)) then if all possible triples are used the number of competitions that would be held in building (i) is [ F(x_i,N)=\sum_{j=0}^{x_i-1} (L+x_i)\quad\text{with}\quad L=\text{the number of players in buildings }1\text{ to }i-1\text{ and }R=N-L-x_i,] which, after a short analysis, can be shown to be maximized (for fixed (x_i) and total (N)) when the players not in building (i) are as evenly distributed as possible before and after building (i). In this case one can prove that [ F(x_i,N)=x_i\cdot L\cdot R+\frac{x_i(x_i-1)(N-x_i)}{2}+\frac{x_i(x_i-1)(x_i-2)}{6}, ] where (L=\lfloor\frac{N-x_i}{2}\rfloor) and (R=N-x_i-\lfloor\frac{N-x_i}{2}\rfloor.)

Since we are allowed to select only some of the possible competitions (each triple of players can be used at most once), a necessary and sufficient condition to achieve the required number of tournaments in building (i) is that the maximum possible number of tournaments (F(x_i,N)) (for the chosen number (x_i) players in building (i)) is at least (a_i). In addition, note that if (a_i>0) then we must have at least one player in building (i) (and in fact at least two players if (i=1) or (i=n) since otherwise no triple can have its median equal to an extreme building). Also, every competition is a triple drawn from the overall (N=\sum_{i=1}^n x_i) players so the total number of competitions when all possible triples are taken is ({N\choose 3}); hence we must have: [ \sum_{i=1}^n a_i\le {N\choose 3}. ]

The problem then reduces to: find the minimum (N) for which there exist nonnegative integers (x_1,x_2,\dots,x_n) (with (x_i\ge 1) if (a_i>0) and (x_1,x_n\ge2) when required) and a choice of numbers (x_i) so that (F(x_i,N)\ge a_i) for all (i) and (\sum_{i=1}^n x_i=N).

One way to solve this is to use a binary search on (N) (the total number of players) starting from the smallest (N) satisfying ({N\choose 3}\ge \sum_{i=1}^n a_i) and then, for each building (i) with (a_i>0), determine the minimum number of players (x_i) needed (under an optimal allocation of the other (N-x_i) players evenly before and after building (i)) so that the maximum possible number of competitions \n(F(x_i,N)) is at least (a_i). If the sum of these minimum requirements does not exceed (N) then such a distribution exists. Otherwise, one must try a larger (N).

Your task is to implement this procedure. (It can be proved that an answer always exists.)

inputFormat

The first line contains a single integer \(n\) (the number of buildings).

The second line contains \(n\) space‑separated nonnegative integers \(a_1,a_2,\dots,a_n\), where \(a_i\) is the number of competitions held in building \(i\).

outputFormat

Output a single integer: the minimum total number \(N\) of players required.

sample

3
0 0 0

0