InternDoor

Where the two sides weigh the same

Easyarrays · prefix sumsRead the input, print the output

Reported in interviews at (where)

You are given a list of whole numbers. A position balances the list when the numbers before it add up to the same total as the numbers after it; the number at the position itself counts on neither side, and an empty side adds up to 0.

For each list, find the first position that balances it. Positions are counted from 0.

Input

The first line holds T, the number of tests. Each test is two lines: n, then the n whole numbers of the list, separated by spaces.

Output

For each test, one line: the first position that balances its list, or -1 if none does.

Example
Input
3
7
1 7 3 6 5 6 0
3
1 2 3
1
-4
Output
3
-1
0
  1. Before position 3: 1 + 7 + 3 = 11. After it: 5 + 6 + 0 = 11.
  2. The sides at positions 0, 1 and 2 are 0 and 5, 1 and 3, 3 and 0.
  3. Both sides of the only position are empty.

Limits

  • 1 <= T <= 200
  • 1 <= n <= 100000
  • -10000 <= each number <= 10000
  • the n of all the tests add up to at most 400000

Hints

Hint 1

The total of the whole list tells you the right side once you know the left side.

Hint 2

Walk once from the left, keeping the sum of what you have passed: the right side is total - left - a[i].

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.