Educational Codeforces Round 42 (Rated for Div. 2) A

A. Equator

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp has created his own training plan to prepare for the programming contests. He will train for $\mathrm{nn days,\; all\; days\; are\; numbered\; from 11to nn,\; beginning\; from\; the\; first.}$

On the $\mathrm{ii-th\; day\; Polycarp\; will\; necessarily\; solve aiai problems.\; One\; evening\; Polycarp\; plans\; to\; celebrate\; the equator.\; He\; will\; celebrate\; it\; on\; the\; first\; evening\; of\; such\; a\; day\; that\; from\; the\; beginning\; of\; the\; training\; and\; to\; this\; day\; inclusive\; he\; will\; solve\; half\; or\; more\; of\; all\; the\; problems.}$

Determine the index of day when Polycarp will celebrate the equator.

Input

The first line contains a single integer $\mathrm{nn (1\le n\le 2000001\le n\le 200000)\; —\; the\; number\; of\; days\; to\; prepare\; for\; the\; programming\; contests.}$

The second line contains a sequence ${\mathrm{a1,a2,\dots ,ana1,a2,\dots ,an (1\le ai\le 100001\le ai\le 10000),\; where aiai equals\; to\; the\; number\; of\; problems,\; which\; Polycarp\; will\; solve\; on\; the ii-th\; day.}}^{}$

Output

Print the index of the day when Polycarp will celebrate the equator.

Examples

input

Copy

4
1 3 2 1

output

Copy

2

input

Copy

6
2 2 2 2 2 2

output

Copy

3

Note

In the first example Polycarp will celebrate the equator on the evening of the second day, because up to this day (inclusive) he will solve $\mathrm{44out\; of 77 scheduled\; problems\; on\; four\; days\; of\; the\; training.}$

In the second example Polycarp will celebrate the equator on the evening of the third day, because up to this day (inclusive) he will solve $\mathrm{66out\; of 1212 scheduled\; problems\; on\; six\; days\; of\; the\; training.}$

 题意：求一组数据中大于等于和的一半的数的位置在哪

tips：一开始我用的是找的 t>sum/2的位置，然后被hack了，冷静分析了一波

如果输入的数据是      6     1 2 3 1 2 4时

得到的答案是 

但是实际上应该是4，因为 ‘/’ 这个是向0取整，所sum/2=6，但是在i=3这个地方时 t=6，所以为了‘/’所产生的误差 就用t*2>sum来判断 就不会产生误差

实际上是一个水题，但是要注意细节

附上代码

#include<bits/stdc++.h>
using namespace std;
const int maxx=200005;
typedef long long ll;
int a[maxx];
int main()
{
    int n;
    ll s=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        s+=a[i];
    }
    ll t=0;
    for(int i=1;i<=n;i++){
        t+=a[i];
        if(t*2>=s){
            printf("%d
",i);
            break;
        }
    }
    return 0;
}