Корвин и Блейз готовятся ко вторжению в Амбер, чтобы свергнуть Эрика. Для этого им нужно собрать армию. В мире, где они находятся есть n поселений, расположенных в линию из-за особенностей местности. Известно, что в первом поселении есть a1 воинов, во втором - a2, в i-ом - ai, в n-ом - an.
Иногда Корвин и Блейз узнают, что в
ai поселении иное количество воинов, чем предполагалось. Корвин и Блейз спрашивают вас
m раз, какое максимальное количество воинов, имеющееся в каком-либо поселении может предоставить наибольшее число воинов. Помогите им определить это.
Входные данные
В первой строке на вход подаются числа 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".
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 3
1 2 3 4 5
0 1 5
1 3 6
0 1 5
|
5
-1
6
|