Точка равновесия на стадионе

На школьном стадионе тренер раскладывает вдоль дорожки таблички с числами — это «баллы нагрузки» на каждом отрезке круга.

Тренер хочет найти такое место разреза после некоторого отрезка, чтобы сумма баллов слева (от начала до этого места) ровно совпала с суммой баллов справа (от следующего отрезка до конца).

Найди самый ранний (с наименьшим номером) разрез, где это получается.

Формат ввода

• В первой строке дано целое число n — количество отрезков (2 ≤ n ≤ 8000).
• Во второй строке дано n целых чисел a1, a2, ..., an — баллы нагрузки (-1000000 ≤ ai ≤ 1000000).

Разрез после i означает, что слева стоят элементы a1..ai, а справа — a(i+1)..an.

Формат вывода Выведи одно целое число — минимальный i (1 ≤ i ≤ n-1), для которого a1 + ... + ai = a(i+1) + ... + an. Если такого i нет, выведи -1.

Ограничения

• 2 ≤ n ≤ 35000
• -1000000 ≤ ai ≤ 1000000

Пример Ввод:

5
1 2 3 3 9

Вывод:

4

После 4-го отрезка слева сумма 1+2+3+3=9, справа сумма 9 — равенство выполнено.

Ключевое наблюдение: пересчитывать сумму справа каждый раз не нужно. Если известна общая сумма total, то сумма справа после разреза i равна total - left, где left — сумма a1..ai. Тогда условие равновесия — это просто left == total - left.

Почему это работает: при проходе по массиву мы поддерживаем одну переменную left (префиксную сумму) и за O(1) узнаём правую часть. Получаем линейное решение вместо квадратичного.

План:

• Считай n и массив a.
• Найди total = sum(a).
• Заведи left = 0.
• Для i от 1 до n-1:
• добавь текущий элемент: left += a[i-1].
• правая сумма: right = total - left.
• если left == right, сразу выведи i (это будет самый ранний разрез) и закончи.
• Если цикл закончился без совпадения — выведи -1.

Сниппет-формула: right = total - left.

Сложность: O(n) по времени и O(1) по памяти (если не считать сам массив).

Частая ошибка: проверять разрез после n (справа пусто) или забыть, что нужен i в диапазоне 1..n-1. Ещё одна грабля — путаница индексов: в коде чаще a[i-1], а выводить нужно человеческий i.