Truy vấn Tổng Đoạn Con Lớn Nhất

Cho mảng $n$ số nguyên. Thực hiện $m$ cập nhật, mỗi cập nhật thay đổi một phần tử. Sau mỗi cập nhật, tính tổng lớn nhất của một đoạn con liên tiếp (đoạn rỗng có tổng bằng 0).

Dữ liệu vào

• Dòng đầu: hai số nguyên $n$ và $m$.
• Dòng thứ hai: $n$ số nguyên $x_1,x_2,\dots ,x_n$.
• $m$ dòng tiếp theo: mỗi dòng chứa hai số $k$ và $x$ — gán $x_k=x$.

Dữ liệu ra

Với mỗi cập nhật, in ra một dòng chứa tổng đoạn con lớn nhất.

Ràng buộc

• $1\le n,m\le 2\times {10}^5$
• $-{10}^9\le x_i,x\le {10}^9$
• $1\le k\le n$

Ví dụ