Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Elections

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAwruk 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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2018 23:24:35 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|