Truy vấn tổng đoạn con lớn nhất III (Can you answer these queries III)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Cho dãy $A_1,A_2,\ldots,A_N$. Có hai loại thao tác:

• 0 x y: gán $A_x=y$.
• 1 x y: in tổng lớn nhất của một đoạn con liên tiếp, không rỗng, nằm trong $[x,y]$.

Input

Dòng đầu chứa $N$.

Dòng thứ hai chứa dãy $A$.

Dòng thứ ba chứa $Q$.

$Q$ dòng tiếp theo mô tả các thao tác.

Output

Với mỗi thao tác loại 1, in đáp án trên một dòng.

Subtask

• Subtask 1 — 20%: $1\le N,Q\le 50$, $|A_i|,|y|\le 1000$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$, $|A_i|,|y|\le 10^4$.
• Subtask 3 — 50%: $1\le N,Q\le 50000$, $|A_i|,|y|\le 10^4$.

Ví dụ

Input

4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3

Output

6
4
-3

Giải thích

Sau khi gán phần tử thứ $3$ thành $-3$, truy vấn $[2,4]$ có đoạn con tốt nhất là $[4]$ với tổng $4$.