Partition Index

You are given an array of (N) positive integers. Your task is to determine whether the array can be partitioned into two non-empty contiguous subarrays such that the sum of the first subarray equals the sum of the second subarray. More formally, find an index (i) (with (1 \le i < N)) such that [ \sum_{k=1}^{i} A_k = \sum_{k=i+1}^{N} A_k ] If such an index exists, output it. Otherwise, output (-1). Note that (2 \le N \le 10^{5}) and (1 \le A_i \le 10^{9}).

inputFormat

The input is read from standard input. The first line contains a single integer (N), the length of the array. The second line contains (N) space-separated integers denoting the elements of the array.

outputFormat

Output a single integer on standard output: the partition index (1-indexed) if a valid partition exists, or (-1) if no such partition exists.## sample

6
1 2 3 3 2 1

3