Приключение Незнайки и его друзей
Приключение Незнайки и его друзей
Все мы помним историю о том, как Незнайка со своими друзьями летали на воздушном шаре путешествовать. Но не все знают, что не все человечки влезли в шар, так как у него была ограниченная грузоподъемность.
В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.
Входные данные
В первой строке содержится количество человечков n~(1 \le n \le 10^6) в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают 10^9. Далее следует количество запросов m~(1 \le m \le 10^5). Каждый запрос представляет собой одну строку. Первое число t в строке — тип запроса.
Если t = 1, то далее следует еще одно число v~(1 \le v \le 10^9) — грузоподъемность воздушного шара.
Если t = 2, то далее следует два числа x~(1 \le x \le n) и y~(1 \le y \le 10^9) — вес человечка на позиции x становится равным y.
Выходные данные
Для каждого запроса с номером 1 выведите в отдельной строке количество человечков, поместившихся в шар.
Пример
5 1 2 3 4 5 5 1 7 1 3 2 1 5 1 7 1 3
3 2 2 0