eolymp
bolt
Try our new interface for solving problems
Problems

Винни-Пух

Винни-Пух

Time limit 2 seconds
Memory limit 64 MiB

Всем известно, что больше всего любит Винни-Пух – конечно же, мед. Вот и сегодня утром медвежонок захотел полакомиться медком. В его погребе на полке стоит N бочонков меда, пронумерованных от 1 до N по порядку. По необъяснимым причинам во всех бочонках находится мед разной "сладости", поэтому, чтобы не расстраиваться Винни может завтракать так, чтобы каждый следующий бочонок был не менее сладким, чем предыдущий. Кроме того, он всегда ест мед по порядку, чтобы не сбиться. Ваша задача посчитать, максимальное количество бочонков сможет съесть медвежонок, следуя его правилам.

Input data

В первой строке находится одно число N (1N10^6) – количество бочонков в погребе Винни-Пуха. В следующей строке находится N чисел – сладости бочонков (все числа не превышают 10^9). Далее следует число M (1M10^5) количество запросов. В последующих М строках находится по три числа: тип запроса, l и r (1lrN). Для каждого запроса с номером один посчитайте ответ на задачу. Запрос с номером 2 означает, что в бочонке под номером l изменилась сладость и теперь она равна r.

Output data

Для каждого запроса с номером один выведите максимальное количество бочонков на промежутке [l; r], которые идут подряд и сладость всех, кроме первого не меньшая сладости предыдущего.

Examples

Input example #1
10
1 2 3 4 2 4 3 6 5 7
6
1 1 10
1 4 6
2 5 4
1 4 6
1 1 2
1 8 9
Output example #1
4
2
3
2
1
Author Alexandr Burkov
Source Distance Summer Computer School - Summer 2013