O34. Саша и кофе

Автор:Завгороднев А.А., Бадерик П.М.  
Входной файл:Стандартный вход  
Выходной файл:Стандартный выход  

Программист Саша пьет кофе всегда из одной и той же кружки, которую он никогда не моет.

Когда кофе находится в кружке достаточно долго, оно оставляет на ней кофейное кольцо.

Иногда Саша подливает кофе в кружку, от чего уровень кофе поднимается, и все кольца, которые оказываются ниже уровня кофе растворяются.

Саша может выполнить 3 действия:

  1. Налить в кружку coffeei миллилитров кофе.
  2. Выпить coffeei миллилитров кофе.
  3. Определить сколько кофейных колец сейчас на кружке.

Считаем, что после каждого действия Саши кофе в кружке стоит достаточно долго, чтобы кольцо успело образоваться.

Формат входных данных

Первая строка входных данных содержит число n - количество действий, которые сделал Саша.

В следующих n строках идет:

Гарантируется, что Саша не пытается выпить больше кофе, чем есть в кружке. Изначально в кружке нет ни миллилитра кофе.

Формат выходных данных

Требуется вывести количество кофейных колец, которое было на кружке после каждого действия Саши. Каждое в новой строке.

Ограничения

0 < n ≤ 107

0 < сi ≤ 108

Гарантируется, что объем кофе в стакане никогда не достигнет 232.

Примеры тестов

Стандартный вход Стандартный выход
1
14
+ 108
+ 105
+ 110
+ 101
- 32
+ 32
+ 32
+ 32
+ 32
- 103
- 114
- 101
- 101
- 100
1
1
1
1
2
1
1
1
1
2
3
4
5
6
2
9
+ 1
- 1
+ 1
+ 1
+ 2
+ 3
- 4
+ 1
+ 7
1
1
1
1
1
1
2
2
1

0.091s 0.010s 13