好多盤子喔~!

題目敘述

「電競牙刷，你一定要擁有的電競好夥伴！」一旁的海報寫著實用商品的宣傳話語。

這裡是電競專賣會，販賣各種實用又炫砲的電競商品。你現在人在電競牙刷的賣場，有$N$個人排隊著，打算搶購待會即將開賣的電競牙刷。不過現在還不知道電競牙刷的售價為何，而每個人$i$都有自己的預估花費金額$P_i$元，表示他們分別願意花多少錢來買電競牙刷。

心動動的你冒出了一個疑問：「如果知道每個人的預估花費金額，能不能有效地求得連續一群人的盤子度呢？」(盤子度的定義請參考下面)

將一群人$[l,r]$分成前後兩群人$[l,m]$和$[m+1,r]$，則這群人$[l,r]$的盤子切割值為：前半群人$[l,m]$的最大預估花費金額減去後半群人$[m+1,r]$的最小預估花費金額，也就是$\max_{P_l,P_{l+1}...P_m} - \min_{P_{m+1},P_{m+2}...P_r}$。

一群人$[l,r]$的盤子度為他們最大的盤子切割值。(根據切割人群的方法不同，盤子切割值也會不一樣，你需要找出最大的那個！)

你想要多次地求得連續一群人的盤子度，而有時候有些人的預估花費金額可能會改變。

輸入說明

第一行給定兩個整數$N(2\leq N\leq 10^5)$與$Q(1\leq Q\leq 10^5)$，以空白間隔，表示有$N$個人排隊及有$Q$筆事件。

第二行有$N$個以空白間隔的整數$P_1,P_2...P_N (0\leq |P_i|\leq 2*10^9)$，表示每個人的預估花費金額。

接下來$Q$行，每行先給定一個整數$t(1\leq t\leq 2)$，表示事件類型。若$t=1$，表示有人預估花費金額改變了，接著會有兩個整數$p(1\leq p\leq N)$和$v(0\leq |v|\leq 2*10^9)$，表示隊伍中第$p$個人的預估花費金額更改為$v$；若$t=2$，接著給定兩個整數$l$和$r(1\leq l<r\leq N)$表示你想要知道連續的一群人$[l,r]$的盤子度。

輸出說明

對於所有$t=2$的事件，輸出一個整數表示他們的盤子度並換行。

範例輸入

8 5
8 3 7 1 1 4 2 5
2 1 6
1 3 -3
2 1 6
2 4 5
2 5 8

範例輸出

子任務

子任務一($5\%$)：$N,Q\leq 500$
子任務二($15\%$)：$N,Q\leq 3000$
子任務三($15\%$)：任意時刻所有人的預估花費金額非嚴格遞減，即 $P_i\geq P_{i+1}$
子任務四($27\%$)：所有人的預估花費金額皆不會改變
子任務五($38\%$)：無限制

提示

好大隻的姆咪

Judge Setting

run-time limit: 1000 ms
memory limit: 538443776 byte
測資數量: 25