Mizuyokan là một loại bánh ngọt Nhật Bản, được làm bằng cách đổ nhân chủ yếu từ đậu đỏ vào khuôn rồi làm đông bằng thạch agar.

JOI có một máy làm mizuyokan hình hộp chữ nhật dài theo phương ngang. Trên bánh có \(N-1\) đường cắt theo phương dọc. Chiều dài bánh và vị trí các đường cắt được xác định bởi \(N\) tham số \(d_1,d_2,\ldots,d_N\): tổng chiều dài là \(d_1+d_2+\cdots+d_N\), và khoảng cách giữa đường cắt thứ \(i-1\) và thứ \(i\) từ trái sang phải là \(d_i\). Quy ước đầu trái là đường cắt thứ \(0\), đầu phải là đường cắt thứ \(N\). Ban đầu, \(d_i=L_i\).

JOI dự định tổ chức \(Q\) buổi tiệc trà theo thứ tự. Buổi thứ \(j\) được mô tả bằng bốn số nguyên \(X_j,Y_j,A_j,B_j\) và diễn ra như sau:

1. Cập nhật tham số \(d_{X_j}\) thành \(Y_j\). Các cập nhật được giữ lại cho những buổi sau.
2. Làm một chiếc bánh mới, lấy phần nằm giữa đường cắt thứ \(A_j\) và thứ \(B_j\) để dùng trong buổi tiệc. JOI ăn phần còn lại.
3. Cắt phần bánh dành cho buổi tiệc tại một số đường cắt thành ít nhất một miếng, sao cho dãy độ dài các miếng, theo thứ tự vị trí ban đầu từ trái sang phải, là một dãy zíc zắc.

Dãy zíc zắc là dãy có các phần tử luân phiên tăng và giảm nghiêm ngặt. Chẳng hạn, \((2,9,2,7)\), \((7,1,9,4,6)\), \((5)\) và \((2,1)\) là các dãy zíc zắc; còn \((1,2,3)\), \((7,1,4,4,6)\) và \((2,2)\) thì không. Chính xác hơn, dãy \((x_1,x_2,\ldots,x_m)\) là zíc zắc nếu thỏa mãn ít nhất một trong hai điều kiện:

• Với mọi \(k=1,2,\ldots,m-1\): nếu \(k\) lẻ thì \(x_k<x_{k+1}\), nếu \(k\) chẵn thì \(x_k>x_{k+1}\).
• Với mọi \(k=1,2,\ldots,m-1\): nếu \(k\) lẻ thì \(x_k>x_{k+1}\), nếu \(k\) chẵn thì \(x_k<x_{k+1}\).

Để mời được nhiều bạn nhất, JOI muốn tối đa hóa số miếng thu được ở bước \(3\) của mỗi buổi tiệc. Cho các tham số ban đầu và kế hoạch các buổi tiệc, hãy tính số miếng lớn nhất cho từng buổi. Với các ràng buộc của bài, luôn tồn tại cách chia thỏa mãn điều kiện.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N
L_1 L_2 ... L_N
Q
X_1 Y_1 A_1 B_1
X_2 Y_2 A_2 B_2
...
X_Q Y_Q A_Q B_Q

Dữ liệu ra

In \(Q\) dòng ra đầu ra chuẩn. Dòng \(j\) chứa số miếng lớn nhất có thể thu được bằng cách chia hợp lệ trong buổi tiệc thứ \(j\).

Ràng buộc

• \(1\le N\le 250\,000\).
• \(1\le L_i\le 10^9\) với \(1\le i\le N\).
• \(1\le Q\le 50\,000\).
• \(1\le X_j\le N\), \(1\le Y_j\le 10^9\) với \(1\le j\le Q\).
• \(0\le A_j<B_j\le N\) với \(1\le j\le Q\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (6 điểm): \(N\le 200\), \(Q\le 10\).
• Nhóm 2 (9 điểm): \(N\le 2000\), \(Q\le 10\).
• Nhóm 3 (13 điểm): \(Q\le 10\).
• Nhóm 4 (32 điểm): \(Y_j=L_{X_j}\) với mọi \(1\le j\le Q\), trong đó \(L\) là các giá trị ban đầu.
• Nhóm 5 (29 điểm): \(L_i\le 120\,000\) với mọi \(1\le i\le N\) và \(Y_j\le 120\,000\) với mọi \(1\le j\le Q\).
• Nhóm 6 (11 điểm): Không có ràng buộc bổ sung.

Ví dụ

6
5 6 8 7 4 9
1
6 9 0 5

3

4
6 2 3 6
3
3 2 1 3
4 5 1 4
1 1 0 4

1
2
3

Nguồn

JOI 2022/2023 Spring Training, Contest 2, 20/03/2023. Đề gốc của JCIOI; bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.