INTVSUM
You are given a sequence ,
,
consisting of
positive integers.
We are asked to determine if there exist positions
and
, with
, such that
, meaning the sum of the numbers at positions
and
in the sequence equals the sum of the numbers at the positions between
and
.
If there are multiple such pairs
in the sequence, we need to calculate the maximum position
for which the above relation holds.
Input
The first line of input will contain the number of elements in the sequence, .
The second line of input will contain
positive integers separated by spaces, representing the sequence.
Output
The output should consist of a single line containing one integer , which corresponds to the maximum position in the sequence for which there exists a position
(with
) such that
.
If no such position exists, the output should be
.
Constraints
.
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
Comments