e-olymp
Задачи

Приключение Незнайки и его друзей

Приключение Незнайки и его друзей

prb4496 Все мы помним историю о том, как Незнайка со своими друзьями летали на воздушном шаре путешествовать. Но не все знают, что не все человечки влезли в шар, так как у него была ограниченная грузоподъемность.

В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.

Входные данные

В первой строке содержится количество человечков n (1n106) в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают 109. Далее следует количество запросов m (1m105). Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число v (1v109) – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа x (1xn) и y (1y109) - это значит, что вес человечка, стоящего на позиции x, теперь равен y.

Выходные данные

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

Лимит времени 1 секунда
Лимит использования памяти 122.17 MiB
Входные данные #1
5
1 2 3 4 5
5
1 7
1 3
2 1 5
1 7
1 3
Выходные данные #1
3
2
2
0
Автор Александр Бурков
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года