Minimum Tokens Remaining

There are infinitely many stacks numbered from 0. The heights of the first N stacks are given, and the rest are empty. Each operation takes 2 tokens from one stack and adds 1 token to the next stack. Find the minimum total number of tokens after any number of operations.

This site uses a standard input/output protocol.

输入格式

The first line contains N, and the second line contains N heights. This site uses 1≤N≤200000 and heights 0..10⁹.

输出格式

Output a single integer, the answer.

样例 1

输入：

2
2 3

输出：

1

样例 2

输入：

2
0 0

输出：

0

样例 3

输入：

1
3

输出：

2

样例说明

Example 1: the total weight is 2+3×2=8, ending with 1 token on stack 3. Example 2: there are no tokens, so 0. Example 3: 3 tokens can become 1 token each on stacks 0 and 1, for 2 tokens in total.