Знаете ли вы, почему так важно правильно составлять техзадание? Устраивайтесь поудобнее, сейчас мы расскажем вам страшную историю про одну строительную компанию, которая не придавала техзаданию должного внимания.

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

1. Изменить количество этажей в i-м здании до x, то есть, если этажей было больше, то их разбирают, а если меньше — то достраивают.
2. Изменить внешнюю отделку стен всех зданий на уровне x-го этажа. Один рабочий может выполнить отделку на непрерывном отрезке зданий, высота каждого из которых составляет хотя бы x этажей.

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

В первой строке дано целое число n (1 ≤ n ≤ 10⁵) — количество зданий.

Во второй строке даны n целых чисел h_i (1 ≤ h_i ≤ 10⁹) — изначальные высоты зданий в порядке слева направо.

В третьей строке дано целое число q (1 ≤ q ≤ 10⁵) — количество изменений.

В следующих q строках описаны изменения в порядке их выполнения. Первое число в каждой строке — это тип изменения (1 или 2).

Если текущее изменение имеет тип 1, то далее следуют целые числа i и x (1 ≤ i ≤ n; 1 ≤ x ≤ 10⁹) — номер здания и новое количество этажей в нём соответственно. Здания пронумерованы, начиная с единицы.

Если текущее изменение имеет тип 2, то далее следует целое число x (1 ≤ x ≤ 10⁹) — высота в этажах, на уровне которой требуется изменение внешней отделки. Гарантируется, что хотя бы одно изменение имеет тип 2.

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

Иллюстрация первых трёх изменений типа 2 из примера: