Equilibrium Index

Difficulty: 1200 2000 ms 128 MB

prefix-sums

Find the smallest index i whose left part sum equals its right part sum (element i excluded from both). Print the 1-based index, or −1.

Input: the first line has N; the second line has N integers.

Output: the smallest equilibrium index (1-based), or −1.

Constraints:

• 1 ≤ N ≤ 10⁵
• −10⁴ ≤ a_i ≤ 10⁴

Sample Tests

5
1 3 5 2 2

3

1
9

1

Read the Editorial