ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2133. Техническое задание

Ограничение времени: 3.0 секунды
Ограничение памяти: 256 МБ
Техническое задание (техзадание) — документ, оговаривающий набор требований к продукту и утверждённый как заказчиком, так и исполнителем.
Энциклопедия
Знаете ли вы, почему так важно правильно составлять техзадание? Устраивайтесь поудобнее, сейчас мы расскажем вам страшную историю про одну строительную компанию, которая не придавала техзаданию должного внимания.
Как-то эта компания строила жилой комплекс, состоящий из n высотных зданий, стоящих вплотную друг к другу. В договоре с заказчиком не было обговорено количество этажей в каждом здании и внешняя отделка стен. Поэтому в течение q дней заказчик изменял требования, а строительной компании приходилось переделывать уже возведённые здания. Изменения бывали одного из двух типов:
  1. Изменить количество этажей в i-м здании до x, то есть, если этажей было больше, то их разбирают, а если меньше — то достраивают.
  2. Изменить внешнюю отделку стен всех зданий на уровне x-го этажа. Один рабочий может выполнить отделку на непрерывном отрезке зданий, высота каждого из которых составляет хотя бы x этажей.
Помогите начальнику отдела кадров строительной компании для каждого изменения внешней отделки стен узнать минимальное количество рабочих, необходимое для этого.

Исходные данные

В первой строке дано целое число n (1 ≤ n ≤ 105) — количество зданий.
Во второй строке даны n целых чисел hi (1 ≤ hi ≤ 109) — изначальные высоты зданий в порядке слева направо.
В третьей строке дано целое число q (1 ≤ q ≤ 105) — количество изменений.
В следующих q строках описаны изменения в порядке их выполнения. Первое число в каждой строке — это тип изменения (1 или 2).
Если текущее изменение имеет тип 1, то далее следуют целые числа i и x (1 ≤ in; 1 ≤ x ≤ 109) — номер здания и новое количество этажей в нём соответственно. Здания пронумерованы, начиная с единицы.
Если текущее изменение имеет тип 2, то далее следует целое число x (1 ≤ x ≤ 109) — высота в этажах, на уровне которой требуется изменение внешней отделки. Гарантируется, что хотя бы одно изменение имеет тип 2.

Результат

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

Пример

исходные данныерезультат
7
3 6 5 2 6 1 4
6
2 3
1 6 4
2 3
2 5
1 4 10
2 5
3
2
2
1

Замечания

Иллюстрация первых трёх изменений типа 2 из примера:
Problem illustration
Автор задачи: Никита Сивухин