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

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

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

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

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

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