Truy vấn tổng đoạn con (Subarray Sum Queries)

Nguồn: CSES

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

Cho mảng $A$ gồm $N$ số nguyên. Có $Q$ lần cập nhật. Mỗi lần cập nhật cho $k,x$ và gán $A_k=x$. Sau mỗi cập nhật, hãy in tổng lớn nhất của một đoạn con liên tiếp trong toàn mảng.

Được phép chọn đoạn rỗng, có tổng bằng $0$.

Input

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

Dòng thứ hai chứa $A_1,\ldots,A_N$.

$Q$ dòng tiếp theo, mỗi dòng chứa $k,x$.

Output

Sau mỗi cập nhật, in tổng đoạn con lớn nhất.

Subtask

• Subtask 1 — 20%: $1\le N,Q\le 50$, $|A_i|,|x|\le 10^4$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$, $|A_i|,|x|\le 10^9$.
• Subtask 3 — 50%: $1\le N,Q\le 2\cdot 10^5$, $|A_i|,|x|\le 10^9$.

Ví dụ

Input

5 3
1 2 -3 5 -1
2 6
3 1
2 -2

Output

9
13
6

Giải thích

Sau mỗi cập nhật, đáp án được tính trên toàn mảng; vì cho phép đoạn rỗng nên đáp án không bao giờ âm.