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