1. Идея

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

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

Главная идея — заранее знать сумму всех элементов массива, а затем идти слева направо, поддерживая:

• left — сумму элементов строго слева от текущей позиции;
• right — сумму элементов строго справа от текущей позиции.

Тогда для позиции i:

• текущий элемент — a[i];
• сумма справа равна total - left - a[i].

Если left == right, то это точка равновесия. Так как нужно вывести наименьший индекс, достаточно идти слева направо и остановиться на первом подходящем месте.

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

1. Сама выбранная точка не входит ни в левую, ни в правую сумму.

   Поэтому для позиции i:

   • левая сумма — это все элементы до i;
   • правая сумма — это все элементы после i.

2. Если известна общая сумма total, то правую сумму не нужно считать отдельно:

   • right = total - left - a[i].

3. После проверки позиции i можно перейти к следующей:

   • прибавить a[i] к left,
   • и тогда left станет суммой элементов слева для следующей позиции.

4. В массиве могут быть отрицательные числа, но это никак не мешает методу. Мы просто сравниваем две суммы.

5. При n = 1 единственная позиция всегда подходит:

   • слева нет элементов, сумма 0;
   • справа тоже нет элементов, сумма 0.

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 = 0, а слева от первой позиции действительно нет элементов;
• после обработки позиции i мы делаем left += a[i], значит к следующему шагу left становится суммой всех элементов до новой позиции.

Теперь для текущей позиции i сумма элементов справа равна:

total - left - a[i]

Почему так?

• total — сумма всех элементов;
• left — сумма слева;
• a[i] — текущий элемент, который не должен входить ни в одну из сумм.

Значит после вычитания left и a[i] остаётся ровно сумма справа.

Таким образом, условие равновесия для позиции i эквивалентно проверке:

left == total - left - a[i]

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

Мы просматриваем позиции слева направо, поэтому первая найденная подходящая позиция имеет наименьший индекс. Именно её и требует задача.

Если ни для одной позиции равенство не выполнилось, точки равновесия не существует, и ответ -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 total = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        total += a[i];
    }

    long long left = 0;
    for (int i = 0; i < n; i++) {
        long long right = total - 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)