Вам дана последовательность \(a_1, a_2, \ldots, a_n\). Каждый элемент \(a\) равен \(1\) или \(2\).
Выясните, существует ли целое число \(k\) такое, что выполняются следующие условия:
- \(1 \leq k \leq n-1\), и
- \(a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n\).
Если существует несколько \(k\), удовлетворяющих данному условию, выведите наименьшее из них.
Выходные данные
Для каждого набора входных данных, если не существует такого \(k\), выведите \(-1\). В противном случае выведите наименьшее возможное значение \(k\).
Примечание
Для первого набора входных данных \(k=2\) удовлетворяет условию, так как \(a_1 \cdot a_2 = a_3 \cdot a_4 \cdot a_5 \cdot a_6 = 4\). \(k=3\) также удовлетворяет данному условию, но нужно вывести наименьшее подходящее значение.
Для второго набора не существует \(k\), удовлетворяющего условию \(a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n\).
Для третьего набора \(k=1\), \(2\), \(3\) удовлетворяет заданному условию, поэтому ответ \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
2 2 1 2 1 2
3
1 2 1
4
1 1 1 1
|
2
-1
1
|