Growing vegetables is boring.

A farmer has planted $N$ vegetables (numbered from $0$ to $N-1$). Initially, on day $0$, every vegetable has height $0$.

Vegetable $i$ has a maximum height of $V_i$. Each day, its height increases by $1$ until it reaches $V_i$. After reaching its maximum height, its height decreases by $1$ each day until it reaches $0$, after which it stays at $0$.

Formally, on day $d$, the height of vegetable $i$ is $$ \max(0, V_i-|d-V_i|) $$

Unfortunately, the farmer is too lazy to harvest the vegetables more than once. He must choose a single day and harvest all $N$ vegetables on that day.

The amount harvested is equal to the sum of the heights of all vegetables on the chosen day.

Help the farmer determine the maximum total amount of vegetables he can harvest.

Input

The first line contains an integer $N$, the number of vegetables.
The next line contains $N$ integers, where the $i$-th integer is $V_i$, the maximum height of vegetable $i$.

Output

Output one integer, the maximum total height of all vegetables that the farmer can obtain by choosing the best day to harvest them.

Constraints

For all cases, $1\le N\le2\times10^5,\ 1\le V_i\le10^9$
Subtask 1 (21%): $N,V_i\le1000$
Subtask 2 (23%): $N\le2000$
Subtask 3 (25%): $\max V_i\le2\times\min V_i$
Subtask 4 (31%): No additional constraints