A - Elections CodeForces - 1043A 水题一枚

A. Elections

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Awruk is taking part in elections in his school. It is the final round. He has only one opponent — Elodreip. The are nn students in the school. Each student has exactly kk votes and is obligated to use all of them. So Awruk knows that if a person gives aiai votes for Elodreip, than he will get exactly k−aik−ai votes from this person. Of course 0≤k−ai0≤k−ai holds.

Awruk knows that if he loses his life is over. He has been speaking a lot with his friends and now he knows a1,a2,…,ana1,a2,…,an — how many votes for Elodreip each student wants to give. Now he wants to change the number kk to win the elections. Of course he knows that bigger kkmeans bigger chance that somebody may notice that he has changed something and then he will be disqualified.

So, Awruk knows a1,a2,…,ana1,a2,…,an — how many votes each student will give to his opponent. Help him select the smallest winning number kk. In order to win, Awruk needs to get strictly more votes than Elodreip.

Input

The first line contains integer nn (1≤n≤1001≤n≤100) — the number of students in the school.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1001≤ai≤100) — the number of votes each student gives to Elodreip.

Output

Output the smallest integer kk (k≥maxaik≥maxai) which gives Awruk the victory. In order to win, Awruk needs to get strictly more votes than Elodreip.

Examples

input

Copy

5 1 1 1 5 1

output

Copy

5

input

Copy

5 2 2 3 2 2

output

Copy

5

Note

In the first example, Elodreip gets 1+1+1+5+1=91+1+1+5+1=9 votes. The smallest possible kk is 55 (it surely can't be less due to the fourth person), and it leads to 4+4+4+0+4=164+4+4+0+4=16 votes for Awruk, which is enough to win.

In the second example, Elodreip gets 1111 votes. If k=4k=4, Awruk gets 99 votes and loses to Elodreip.

分析：水题一枚，但是觉得自己没用暴力枚举很好，虽然用的不是多高深的数学公式。

#include<cstdio>
#include <stdio.h>
#include <stdlib.h>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
using namespace std;
const double eps = 1e-8;
typedef long long LL;
const int M=1005;
int n,m;
int a[M];
int main()
{
    scanf("%d",&n);
    int sum=0,maxx=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        maxx=max(maxx,a[i]);
        sum+=a[i];
    }
    int sum1=0;
    for(int i=1;i<=n;i++)
    {
        sum1+=maxx-a[i];
    }
    if(sum1>sum)
    {
        cout<<maxx<<endl;
        return 0;
    }
    
    int k=(sum-sum1)/n+1;
    
    if(sum1+n*k==sum){k++;}
    cout<<maxx+k<<endl;
    return 0;
}