The popular idol Ninomae Ina'nis is hosting a New Year concert! Many of her fans, known as Takodachis, have come out to watch her perform. At the reception, there are $N$ Takodachis waiting in line. Initially, the $i^{\text{th}}$ Takodachi has height $h_i$. Seeing her Takodachis with different heights, she starts to wonder if the taller ones will block the shorter Takodachis in the concert. That's when she came up with the brilliant idea of making them all have the same height.

To do so, Ina can perform the following operation: choose two Takodachis indexed at $i$ and $j$ such that $i<j$. Then, she will increment the $i^{\text{th}}$ Takodachi's height by $1$ and increment the $j^{\text{th}}$ Takodachi's height by $2$.

What is the minimum possible height such that all Takodachis' height can be equal to it after some, possibly zero, number of operations?

Constraints

$2\le N\le 2\times {10}^5$

$1\le h_i\le {10}^{12}$

Subtask 1 [40%]

$2\le N\le 100$

$1\le h_i\le {10}^3$

Subtask 2 [60%]

No additional constraints.

Input Specification

The first line contains an integer $N$, the number of Takodachis.

The next line contains $N$ space-separated integers, with the $i^{\text{th}}$ integer $h_i$ indicating the height of the $i^{\text{th}}$ Takodachi.

Output Specification

If it is impossible to make all Takodachis the same height, output $-1$.

Otherwise, output the minimum possible height such that all Takodachis can be equal to that height after some, possibly zero, number of operations.

Sample Input

4
1 2 3 4

Sample Output

10