Question
Balance Index in the Array
In a distant village, a young mathematician named Tara has been given a special challenge. She is handed an array A of size N, filled with mystical numbers. Her task is to find the smallest index i (where 1 ≤ i ≤ N) such that the sum of the first i elements is greater than or equal to the sum of the remaining elements of the array. Can you help Tara find this magical index where the balance shifts in her favor?
Input
The first line of the input contains a single integer N.
The second line of the input contains N space-separated integers.
Constraints:
1 ≤ N ≤ 105
1 ≤ Ai ≤ 109
The second line of the input contains N space-separated integers.
Constraints:
1 ≤ N ≤ 105
1 ≤ Ai ≤ 109
Output
Print the smallest index i (1 ≤ i ≤ N) such that the sum of the first i elements is greater than or equal to the sum of the rest of the elements of the array.
Example
Sample Input
5
6 4 7 9 2
Sample Output
3
Explanation
Sum upto i = 3 -> 17
Some of the rest of the array -> 11
5
6 4 7 9 2
Sample Output
3
Explanation
Sum upto i = 3 -> 17
Some of the rest of the array -> 11