Special Index Finder

Given an integer ( n ) and a sequence of ( n ) integers ( a_1, a_2, \dots, a_n ), find a special index ( i ) (1-indexed) such that the product of all numbers before ( i ) equals the product of all numbers after ( i ). In other words, find an index ( i ) satisfying [ \prod_{j=1}^{i-1} a_j = \prod_{j=i+1}^{n} a_j, ] with the convention that an empty product is equal to 1. If such an index exists, print it; otherwise, print -1. Note that when ( n = 1 ), the answer is 1 if ( a_1 = 1 ) and -1 otherwise.

inputFormat

The first line of input contains an integer ( n ) denoting the number of elements in the sequence. The second line contains ( n ) space-separated integers representing the sequence.

outputFormat

Print a single integer: the 1-indexed special index if it exists; otherwise, print -1.## sample

5
1 2 1 1 2

3