#D13107. Elections
Elections
Elections
Awruk is taking part in elections in his school. It is the final round. He has only one opponent — Elodreip. The are n students in the school. Each student has exactly k votes and is obligated to use all of them. So Awruk knows that if a person gives a_i votes for Elodreip, than he will get exactly k - a_i votes from this person. Of course 0 ≤ k - a_i holds.
Awruk knows that if he loses his life is over. He has been speaking a lot with his friends and now he knows a_1, a_2, ..., a_n — how many votes for Elodreip each student wants to give. Now he wants to change the number k to win the elections. Of course he knows that bigger k means bigger chance that somebody may notice that he has changed something and then he will be disqualified.
So, Awruk knows a_1, a_2, ..., a_n — how many votes each student will give to his opponent. Help him select the smallest winning number k. In order to win, Awruk needs to get strictly more votes than Elodreip.
Input
The first line contains integer n (1 ≤ n ≤ 100) — the number of students in the school.
The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 100) — the number of votes each student gives to Elodreip.
Output
Output the smallest integer k (k ≥ max a_i) which gives Awruk the victory. In order to win, Awruk needs to get strictly more votes than Elodreip.
Examples
Input
5 1 1 1 5 1
Output
5
Input
5 2 2 3 2 2
Output
5
Note
In the first example, Elodreip gets 1 + 1 + 1 + 5 + 1 = 9 votes. The smallest possible k is 5 (it surely can't be less due to the fourth person), and it leads to 4 + 4 + 4 + 0 + 4 = 16 votes for Awruk, which is enough to win.
In the second example, Elodreip gets 11 votes. If k = 4, Awruk gets 9 votes and loses to Elodreip.
inputFormat
Input
The first line contains integer n (1 ≤ n ≤ 100) — the number of students in the school.
The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 100) — the number of votes each student gives to Elodreip.
outputFormat
Output
Output the smallest integer k (k ≥ max a_i) which gives Awruk the victory. In order to win, Awruk needs to get strictly more votes than Elodreip.
Examples
Input
5 1 1 1 5 1
Output
5
Input
5 2 2 3 2 2
Output
5
Note
In the first example, Elodreip gets 1 + 1 + 1 + 5 + 1 = 9 votes. The smallest possible k is 5 (it surely can't be less due to the fourth person), and it leads to 4 + 4 + 4 + 0 + 4 = 16 votes for Awruk, which is enough to win.
In the second example, Elodreip gets 11 votes. If k = 4, Awruk gets 9 votes and loses to Elodreip.
样例
5
2 2 3 2 2
5