1. Идея

Нужно найти такую позицию i, что сумма всех элементов слева от неё равна сумме всех элементов справа от неё.

Если проверять каждую позицию отдельно и каждый раз заново считать суммы слева и справа, получится слишком медленно: до O(n^2).

Поэтому используем более удобный подход:

• сначала посчитаем сумму всех грузов sum;
• затем будем идти слева направо и поддерживать сумму слева left;
• для текущей позиции i сумма справа легко находится как sum - left - a[i].

Если в какой-то позиции left == right, то это и есть точка равновесия. Так как идём слева направо, первая найденная позиция автоматически будет с минимальным индексом.

2. Наблюдения

Наблюдение 1

Для позиции i:

• слева находятся элементы a[0] ... a[i-1],
• справа находятся элементы a[i+1] ... a[n-1],
• элемент a[i] в сравнение не входит.

Значит:

• сумма слева равна left,
• сумма справа равна total - left - a[i].

Наблюдение 2

Если идти по массиву слева направо, то left можно обновлять очень просто:

• сначала left = 0,
• после обработки позиции i делаем left += a[i].

Наблюдение 3

Нужно вывести наименьший индекс. Поэтому достаточно найти первую подходящую позицию и сразу завершить программу.

Наблюдение 4

Сумма элементов может быть большой:

• n до 2 * 10^5,
• a_i до 10^9.

Максимальная сумма порядка 2 * 10^14, поэтому в C++ нужен тип long long.

3. Алгоритм

1. Считываем n и массив a.
2. Находим сумму всех элементов total.
3. Заводим переменную left = 0.
4. Для каждой позиции i от 0 до n - 1:
   • вычисляем right = total - left - a[i];
   • если left == right, выводим i + 1 и завершаем программу;
   • иначе добавляем текущий элемент в левую сумму: left += a[i].
5. Если после прохода подходящей позиции не нашлось, выводим -1.

4. Почему это работает

Докажем, что алгоритм действительно находит правильный ответ.

Пусть сейчас рассматривается позиция i.

• Переменная left хранит сумму элементов строго слева от i, потому что мы уже прошли все предыдущие элементы и добавили их в left.
• Сумма элементов справа от i тогда равна общей сумме минус сумма слева минус текущий элемент: total - left - a[i].

Значит, в каждой позиции алгоритм точно проверяет нужное условие задачи: сумма строго слева равна сумме строго справа.

Если равенство выполняется, то позиция подходит.

Почему выводится минимальный индекс?

• Мы проверяем позиции по порядку: 1, 2, ..., n.
• Как только нашли первую подходящую, сразу выводим её и заканчиваем работу.
• Следовательно, найденный индекс — наименьший возможный.

Если же ни в одной позиции равенство не выполнилось, то подходящей точки равновесия не существует, и ответ -1 верен.

5. Сложность

• Подсчёт общей суммы: O(n)
• Один проход по массиву: O(n)

Итого:

• время: O(n)
• память: O(n) на хранение массива

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    long long left = 0;
    for (int i = 0; i < n; i++) {
        long long right = sum - left - a[i];
        if (left == right) {
            cout << (i + 1) << '\n';
            return 0;
        }
        left += a[i];
    }

    cout << -1 << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

total = sum(a)
left = 0

for i in range(n):
    right = total - left - a[i]
    if left == right:
        print(i + 1)
        break
    left += a[i]
else:
    print(-1)