Дан массив целых чисел nums (первый элемент массива имеет индекс 0). Найдите наименьший "средний" индекс массива.
Средний индекс - это индекс, для которого выполняется условие: сумма элементов слева от индекса равна сумме элементов справа от индекса (не включая сам элемент со средним индексом). То есть
leftSum[middle] = rightSum[middle].
Где:
middle - средний индекс массива.
leftSum[middle] - сумма элементов, стоящих слева от элемента nums[middle]. Если таких элементов нет, то leftSum[middle] = 0.
rightSum[middle] - сумма элементов, стоящих справа от элемента nums[middle]. Если таких элементов нет, то rightSum[middle] = 0.
Формат входных данных
Первая строка содержит натуральное число N (1 <= N <= 105) - количество элементов в массиве nums. Вторая строка содержит N чисел numsi - элементы массива nums (|numsi|<=1000, 0 <= i < N).
Формат выходных данных
Выведите одно число - наименьший "средний" индекс массива. Если такого индекса нет, то выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 3 -1 8 4
|
3
|
|
2
|
3
1 -1 4
|
2
|
|
3
|
2
2 5
|
-1
|