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 \le 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, \dots, 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, \dots, 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 \le n \le 100$) — the number of students in the school.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 100$) — the number of votes each student gives to Elodreip.

**Output**

Output the smallest integer $k$ ($k \ge \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.

**Solution:**

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; int k = *max_element(a.begin(), a.end()); int diff = 0; for (int i = 0; i < n; i++) { diff -= k - a[i]; diff += a[i]; } if (diff >= 0) { k += diff / n + 1; } cout << k << '\n'; return 0; }