Problem : 144 - 海綿寶寶之吹泡泡

Problem Statistics

Solved Member: 66　　Submission: 324　　User Tried: 71

Statement:

海綿寶寶最喜歡吹泡泡了>////<，so cute！
今天海綿寶寶的眼睛有點痛，所以沒辦法睜開，但是他又想吹泡泡。
於是他吹了n個泡泡，不巧，這n個泡泡剛好排成一排。
他會給你多次詢問，希望你可以告訴他某個區間內，最高的一個泡泡的高度是多少。
因為空氣浮力不等於泡泡重，所以泡泡會往上飛或往下掉。
因此在詢問中間，你可能需要更新泡泡的高度〈我們假設每個泡泡飛和掉的速度可能不一樣，而且有的會暫時停住不動〉。

Input:Output:

第一行有兩個數字n, q(1≦n≦100000, 0≦q≦100000)，代表總共有n個泡泡〈編號1~n〉以及q個詢問〈包含更新高度以及海綿寶寶的詢問〉。
第二行有n個數字，代表初始時第1個泡泡到第n個泡泡的高度。
接下來有q行，依序代表q次詢問。
詢問可能會是 1 a b 或是 2 l r 。
如果第一個數字是1，代表你要將編號a的泡泡的高度更新成b。
如果第一個數字是2，代表海綿寶寶向你詢問從編號l到編號r的泡泡中，高度最高的泡泡高度是多少。
0 ≦ 任意泡泡的高度 ≦ 1000000000。

請你對於每筆開頭為2的詢問輸出一行，包含一個數字，代表該次詢問的答案。

Sample Input:Sample Output:

5 5
1 2 3 4 5
2 1 3
1 4 7
2 1 5
1 5 9
2 4 5

3
7
9

HINT:

我愛海綿寶寶>///<

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0	3500ms	65536kb
1	3500ms	65536kb	10
2	3500ms	65536kb	10
3	3500ms	65536kb	10
4	3500ms	65536kb	10
5	3500ms	65536kb	10
6	3500ms	65536kb	10
7	3500ms	65536kb	10
8	3500ms	65536kb	10
9	3500ms	65536kb	10
10	3500ms	65536kb	10