Maija has created a new state in southern Finland that she markets as "by the people, for the people". As the state's absolute leader, she wishes to live up to this promise by establishing absolute equality among it's citizens.

The state has n citizens numbered 1,2,\dots,n and the i-th citizen has b_i bottles of thirst management liquid in their possession. Maija wants to distribute them such that every citizen has the exact same number of bottles. She mobilizes the entire workforce of the state to complete this task.

A worker can do one of the following two operations arbitrarily many times.

1. Receive 1 bottle as a gift from citizen i and drink it.
2. Take 2 bottles from citizen i and deliver one of them
   to citizen j. The other bottle mysteriously disappears on the way.

Maija is aware of the way her workers behave, so now she wants to calculate the maximum possible amount of bottles each citizen will have left after equality has been established.

Input

The first line contains a single integer n.

The next line contains n integers b_1,\,b_2,\cdots,\,b_n.

Output

Output the maximum number of bottles each citizen has after equality has been established.

Constraints

• 1 \leq n \leq 2 \times 10^5
• 1 \leq b_i \leq 10^9

Example 1

Input:

6
2 0 9 9 2 4

Output:

3

Explanation:
Let's denote operation 1. with "iX", and operation 2. with "i\rightarrow j". The following sequence equalizes the bottles optimally: 6\rightarrow5, 4\rightarrow6, 3\rightarrow1, 3\rightarrow2, 3\rightarrow2, 4\rightarrow2, 4X, 4X.

Example 2

Input:

1
4

Output:

4

Example 3

Input:

10
1000000000 1000000000 1000000000 1000000000 1000000000 0 20 16 3 2

Output:

333333338