mean

George loves informatics very much, but he is only a beginner and therefore he needs your help.

In the informatics class the teacher writes on the board $N$ integers and George should make several operations. An operation consists in choosing two adjacent integers and replace them with a single number, equal to the integer part of their arithmetic mean. For example, $7$ and $9$ are replaced with $8$, $7$ and $12$ with $9$, $101$ and $102$ with $101$. George should make these operations until there will be only one integer on the board.

Task

Help George find out what is the greatest number which can be obtained in the end.

Input data

The first line of the input contains one integer $N$, representing the number of integers written on the board.

The second line of the input contains $N$ integers $a_1, a_2, \dots a_n$, the numbers written on the board at the beginning.

Output data

The first line of the output contains one integer, the greatest number that can be obtained in the end, after all the operations are made.

Constraints and clarifications

• $1 \leq N \leq 200$
• $1 \leq a_i \leq 1 \ 000 \ 000 \ 000$, for $i$ from $1$ to $N$

Example

stdin

4
2 4 5 7

stdout

5

Explanation

Initial numbers written on the board: $2 \ 4 \ 5 \ 7$

Replace the elements on the positions $2$ and $3$: $2 \ 4 \ 7$

Replace the elements on the positions $1$ and $2$: $3 \ 7$

Replace the elements on the positions $1$ and $2$: $5$