A. Mysterious Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While exploring the ruins of an ancient city, archaeologists discovered a huge wall with an array of non-negative integers $$$a$$$ inscribed on it. After considerable effort, they managed to read the ancient inscriptions and understand that this array could reveal crucial information about the ancient civilization. One of the steps to achieve this is to solve a certain problem related to this array.

You can perform the following operation on the array: choose 2 indices $$$i$$$ and $$$j\, (1 \le i \lt j \le n)$$$, where $$$n$$$ is the length of the array $$$a$$$, and then subtract 2 from $$$a_i$$$ and add 1 to $$$a_j$$$. After each operation, all elements of the array must remain non-negative. You need to determine the maximum number of operations that can be applied to the array $$$a$$$.

Input

The first line contains a single integer $$$n\, (1 \le n \le 10^5)$$$ – the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n\, (0 \le a_i \le 10^9)$$$.

Output

In a single line, output the maximum number of operations that can be performed on the given array $$$a$$$.

Examples
Input
4
3 2 4 5
Output
5
Input
6
1 2 4 1 1 0
Output
6