1. Идея

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

Так как каждое событие меняет баланс на +1 или -1, достаточно идти слева направо, поддерживать текущую префиксную сумму и сразу остановиться, как только она станет меньше нуля.

Если за весь проход этого не произошло, ответ -1.

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

• Баланс после первых i событий — это префиксная сумма a[1] + a[2] + ... + a[i].
• Требуется именно первая позиция, где эта сумма отрицательна.
• Поэтому нет смысла хранить все префиксные суммы: достаточно одной переменной sum.
• Как только sum < 0, можно немедленно вывести текущую позицию, потому что более ранних отрицательных позиций уже не существует — мы просматриваем массив по порядку.

Пример:

• a = [1, -1, -1, 1]
• суммы по префиксам:
  • после 1-го: 1
  • после 2-го: 0
  • после 3-го: -1
• первая отрицательная сумма появилась на позиции 3.

3. Алгоритм

1. Считать n.
2. Завести переменную sum = 0.
3. Для каждой позиции от 1 до n:
   • считать очередное число x;
   • прибавить его к sum;
   • если sum < 0, вывести текущую позицию и завершить программу.
4. Если цикл закончился и отрицательной суммы не было, вывести -1.

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

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

Во время прохода на шаге i переменная sum равна сумме первых i элементов, то есть текущему балансу после i событий. Это верно, потому что мы начинаем с 0 и каждый раз прибавляем очередное изменение.

Далее возможны два случая:

• Если на некоторой позиции i впервые выполняется sum < 0, то баланс после первых i событий отрицателен, а на всех предыдущих позициях он не был отрицательным. Значит, i и есть искомый минимальный индекс.
• Если после обработки всех n элементов ни разу не получилось sum < 0, значит ни одна префиксная сумма не отрицательна. Тогда по условию нужно вывести -1.

Следовательно, алгоритм всегда выводит правильный ответ.

5. Сложность

• Время: O(n), потому что массив просматривается один раз.
• Память:
  • в решении на C++: O(1), так как элементы можно обрабатывать по одному;
  • в решении на Python ниже используется список из входных данных, поэтому O(n).

6. Код на C++17

#include <iostream>
using namespace std;

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

    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
        if (sum < 0) {
            cout << i << '\n';
            return 0;
        }
    }

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

7. Код на Python 3

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

s = 0
for i in range(n):
    s += a[i]
    if s < 0:
        print(i + 1)
        break
else:
    print(-1)