Liones的寶石 2

題目敘述

經由上次的協助後，$Liones$的家中依然有許多閃閃發亮的寶石，一個接一個的直線排列在桌子上，每天$Liones$要出門為自己打扮妝點的時候，就會順手的從桌上抓取一些寶石來配戴在自己身上，凸顯自己的身分地位。每一個寶石對於$Liones$的造型都有不同的加成效果，稱為美感分數，比如說亮眼的紅寶石因為十分的耀眼，有100分的分數，而綠寶石與$Liones$平時的打扮十分不搭，穿上後會獲得$-87$的分數，大量扣分。$Liones$整體的美感分數會是所有穿著在身上寶石美感分數的總和。

不過$Liones$平時十分懶惰，這次她每一次只會抓一把擺放在指定區間中連續的寶石直接穿在身上，但至少會拿一個，而且$Liones$的爸爸為了讓$Liones$有更多選擇，有時會隨機的更換在桌上的寶石，所以每一天$Liones$的美感分數都不一樣，因此$Liones$很好奇自己每天都這樣隨意的抓取寶石下，自己的美感分數最高會是多少，身為僕人的你可以幫忙計算嗎？

輸入說明

測資一開始有一個數字$N$，表示桌上有多少寶石，接下來下一行有$N$個整數$a_1,a_2,\cdots a_N$，依序表示桌上寶石的美感分數。接下來有一個整數$Q$，表示有$Q$個動作。

接下來$Q$行動作有兩種格式

0 L v，表示爸爸把第$L$個寶時更換成美感分數$v$分的寶石。
1 L R，表示$Liones$要從$[L,R]$(含頭尾)之間抓取寶石。
$1\leq Q \leq 10^5$
$1\leq L \leq R \leq N \leq 10^5$
$|a_i|,|v| \leq 10000$。

輸出說明

對於每一個抓取寶石的動作輸出一行，為$Liones$該次可獲得最高的美感分數。

範例輸入

5
2 -9 3 1 -2
5
1 1 5
0 2 -1
1 1 5
1 3 5
1 2 5

範例輸出

限制:

時限	100ms
記憶體	128 MB

提示

Tip:測資很大、線段樹。

Judge Setting

run-time limit: 100 ms
memory limit: 6553600 byte
測資數量: 0