Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Дерево отрезков

Корвин и Блейз готовятся ко вторжению в Амбер, чтобы свергнуть Эрика. Для этого им нужно собрать армию. В мире, где они находятся есть n поселений, расположенных в линию из-за особенностей местностьи. Известно, что в первом поселении есть a1 воинов, во втором - a2, в i-ом - ai, в n-ом - an. 
Иногда Корвин и Блейз узнают, что в  ai поселении иное количество воинов, чем предполагалось. Корвин и Блейз спрашивают вас m раз, какое поселение с номерами от l до r может предоставит наибольшее число воинов. Помогите им определить это.

Входные данные:
В первой строке на вход подаются числа n и m (1 <= n, m <= 100000) - число поселений и число запросов.
Во второй строке находятся n чисел a1, a2, ..., an (1 <= ai <= 1000) - количество воинов в поселениях.
В следующих m строках находятся числа t, l и r (1 <= l <= r <= n), (0 <= t <= 1) - если t равно 0, то l и r - границы запросов. Иначе l - номер города, а r - новая информация.

Выходные данные:
На i-той строке выведите ответ на i-тый запрос, если ti = 0, иначе выведите "-1".

Пример
Ввод
5 3
1 2 3 4 5
0 1 5
1 3 6
0 1 5
 
Вывод
5
-1
6

(с) Григорьев Е., 2016г. 


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: