Codeforces Round 244 (Div. 2) |
---|
Закончено |
Недавно в вашем городе открылось отделение полиции. Сейчас идет набор кадров для работы в новом отделении. А тем временем, преступления все совершаются в городе.
Достоверно известно, что один полицейский может расследовать только одно преступление за всю свою жизнь. Если преступление произошло в тот момент, когда в отделении полиции не было ни одного незанятого преступлениями полицейского, то оно так и останется навсегда нераскрытым.
Вам заданы события в хронологическом порядке. Каждое событие — это: либо совершение преступления, либо прием на работу нового полицейского. Какое минимальное количество преступлений в любом случае останутся нераскрытыми?
В первой строке записано целое число n (1 ≤ n ≤ 105) — количество событий. В следующей строке записано n целых чисел, описывающих события, через пробел.
Если число равняется -1, значит, произошло одно преступление. В противном случае, число будет положительным (не больше 10) и будет равняться количеству полицейских, нанятых в этот момент. События заданы в хронологическом порядке.
Выведите единственное целое число — количество нерасследованных преступлений.
3
-1 -1 1
2
8
1 -1 1 -1 -1 1 1 1
1
11
-1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1
8
Рассмотрим второй тестовый пример:
В итоге одно преступление в любом случае останется нераскрытым. Остальные два могут раскрыть.
Название |
---|