INTVSUM

You are given a sequence ~a_1~, ~...~, ~a_N~ consisting of ~N~ positive integers. We are asked to determine if there exist positions ~i~ and ~j~, with ~i < j~, such that ~a_i + a_j = a_{i+1} + ... + \;a_{j-1}~, meaning the sum of the numbers at positions ~i~ and ~j~ in the sequence equals the sum of the numbers at the positions between ~i~ and ~j~. If there are multiple such pairs ~(i,\;j)~ in the sequence, we need to calculate the maximum position ~j~ for which the above relation holds.

Input

The first line of input will contain the number of elements in the sequence, ~N~. The second line of input will contain ~N~ positive integers separated by spaces, representing the sequence.

Output

The output should consist of a single line containing one integer ~j~, which corresponds to the maximum position in the sequence for which there exists a position ~i~ (with ~i < j~ ) such that ~a_i + a_j = a_{i+1} + ... + \;a_{j-1}~. If no such position exists, the output should be ~0~.

Constraints

~3 \le N \le 100.000~.
Maximum execution time: 1 sec.
Maximum available memory: 16 MB.

Examples of Input - Output

1st

STDIN (intvsum.in)

10
78 14 8 1 2 32 16 45 47 64

STDOUT (intvsum.out)

8

2nd

STDIN (intvsum.in)

10
3 6 1 2 5 1 4 7 14 8

STDOUT (intvsum.out)

9

3d

STDIN (intvsum.in)

10
256 128 64 32 16 32 64 128 256 512

STDOUT (intvsum.out)

0