Mizuyokan là một loại bánh ngọt Nhật Bản làm từ nhân đậu azuki. Bánh được làm bằng cách nấu nhân đậu azuki với agar rồi để đông trong khuôn hình chữ nhật.

Hiện tại, JOI-kun có một máy làm mizuyokan. Nhờ máy này, JOI-kun có thể làm một miếng mizuyokan hình chữ nhật dài theo chiều ngang, có $N-1$ đường cắt dọc. Chiều dài của miếng mizuyokan 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 trên máy. Chiều dài của miếng mizuyokan là $d_1+d_2+\cdots+d_N$. Khoảng cách giữa đường cắt thứ $i-1$ ($1\le i\le N$) từ trái sang và đường cắt thứ $i$ từ trái sang là $d_i$. Ở đây, mép trái của miếng mizuyokan được coi là đường cắt thứ $0$, còn mép phải được coi là đường cắt thứ $N$. Ban đầu, các tham số của máy thỏa mãn $d_i=L_i$ ($1\le i\le N$).

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

1. Tham số $d_{X_j}$ của máy làm mizuyokan được cập nhật thành $Y_j$.
2. JOI-kun dùng máy làm một miếng mizuyokan mới. Cậu lấy phần nằm giữa đường cắt thứ $A_j$ và đường cắt thứ $B_j$ để dùng cho buổi tiệc trà. Cậu ăn phần còn lại.
3. JOI-kun cắt phần mizuyokan dành cho buổi tiệc trà dọc theo một số đường cắt, chia phần đó thành một hoặc nhiều miếng. Trong quá trình này, phải thỏa mãn điều kiện sau: nếu xếp các miếng từ trái sang theo vị trí ban đầu, dãy độ dài của chúng phải zíc zắc.

Một dãy được gọi là zíc zắc nếu các phần tử của nó luân phiên tăng và giảm. Ví dụ, các dãy $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$, $(2,1)$ là zíc zắc, nhưng các dãy $(1,2,3)$, $(7,1,4,4,6)$, $(2,2)$ không phải zíc zắc. Chính xác hơn, dãy $(x_1,x_2,\ldots,x_m)$ được gọi là zíc zắc nếu thỏa mãn một trong hai (hoặc cả hai) điều kiện sau:

• Với $k=1,2,\ldots,m-1$, ta có $x_k<x_{k+1}$ nếu $k$ lẻ, và $x_k>x_{k+1}$ nếu $k$ chẵn.
• Với $k=1,2,\ldots,m-1$, ta có $x_k>x_{k+1}$ nếu $k$ lẻ, và $x_k<x_{k+1}$ nếu $k$ chẵn.

Vì JOI-kun muốn tặng mizuyokan cho càng nhiều bạn càng tốt, cậu muốn tối đa hóa số miếng thu được ở bước 3 của buổi tiệc trà.

Hãy viết chương trình, với thông tin về các tham số ban đầu của máy làm mizuyokan và kế hoạch các buổi tiệc trà, tính cho mỗi buổi tiệc trà số miếng lớn nhất có thể thu được bằng cách cắt phần mizuyokan sao cho thỏa mãn điều kiện. Lưu ý rằng, với các giới hạn của bài toán, luôn có thể cắt phần mizuyokan sao cho thỏa mãn điều kiện.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

$$ \begin{array}{llll} N \\ L_1\ L_2\ \cdots\ L_N \\ Q \\ X_1 & Y_1 & A_1 & B_1 \\ X_2 & Y_2 & A_2 & B_2 \\ \vdots \\ X_Q & Y_Q & A_Q & B_Q \end{array} $$

Dữ liệu ra

Ghi $Q$ dòng ra đầu ra chuẩn. Dòng thứ $j$ ($1\le j\le Q$) tương ứng với buổi tiệc trà thứ $j$, chứa số miếng lớn nhất có thể thu được khi cắt phần mizuyokan trong buổi tiệc trà đó sao cho thỏa mãn điều kiện.

Giới hạn

• $1\le N\le250\,000$.
• $1\le L_i\le10^9$ ($1\le i\le N$).
• $1\le Q\le50\,000$.
• $1\le X_j\le N$ ($1\le j\le Q$).
• $1\le Y_j\le10^9$ ($1\le j\le Q$).
• $0\le A_j<B_j\le N$ ($1\le j\le Q$).
• Tất cả các giá trị đã cho đều là số nguyên.

Nhiệm vụ con

1. (6 điểm) $N\le200$, $Q\le10$.
2. (9 điểm) $N\le2\,000$, $Q\le10$.
3. (13 điểm) $Q\le10$.
4. (32 điểm) $Y_j=L_{X_j}$ ($1\le j\le Q$).
5. (29 điểm) $L_i\le120\,000$ ($1\le i\le N$), $Y_j\le120\,000$ ($1\le j\le Q$).
6. (11 điểm) Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3

Ghi chú

Trong buổi tiệc trà thứ nhất, các tham số của máy được đặt thành $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$. JOI-kun dùng phần mizuyokan nằm giữa đường cắt thứ $0$ và đường cắt thứ $5$, như trong Hình 1.

Hình 1. Phần mizuyokan dành cho buổi tiệc trà

Ví dụ, JOI-kun có thể cắt phần mizuyokan như sau.

Hình 2. Ba cách cắt mizuyokan. Từ trên xuống là Cách 1, Cách 2, Cách 3.

Ở Cách 1, độ dài các miếng là $5,14,7,4$. Vì dãy này không zíc zắc nên không thỏa mãn điều kiện. Ngược lại, ở Cách 2, độ dài các miếng là $11,8,11$. Dãy này zíc zắc nên thỏa mãn điều kiện. Ở Cách 3, độ dài miếng là $30$. Dãy này zíc zắc nên cũng thỏa mãn điều kiện.

Nếu JOI-kun cắt phần mizuyokan theo Cách 2, cậu thu được 3 miếng. Vì không thể cắt phần mizuyokan vừa thỏa mãn điều kiện vừa thu được ít nhất 4 miếng, hãy xuất $3$ ở dòng đầu tiên.

Dữ liệu vào này thỏa mãn các giới hạn của tất cả nhiệm vụ con.

Dữ liệu vào 2

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

Dữ liệu ra 2

1
2
3

Ghi chú

Trong buổi tiệc trà thứ nhất, phần mizuyokan dành cho buổi tiệc trà có độ dài $4$. Có một đường cắt cách mép trái một khoảng $2$. Nếu JOI-kun dùng phần mizuyokan mà không cắt, cậu thu được một miếng. Dãy độ dài các miếng là $(4)$, là dãy zíc zắc. Vì không thể thu được nhiều hơn một miếng, hãy xuất $1$.

Trong buổi tiệc trà thứ hai, phần mizuyokan dành cho buổi tiệc trà có độ dài $9$. Có hai đường cắt cách mép trái các khoảng $2,4$. Nếu JOI-kun cắt tại đường cắt cách mép trái một khoảng $4$, cậu thu được hai miếng. Dãy độ dài các miếng là $(4,5)$, là dãy zíc zắc. Vì không thể thu được nhiều hơn hai miếng, hãy xuất $2$.

Trong buổi tiệc trà thứ ba, phần mizuyokan dành cho buổi tiệc trà có độ dài $10$. Có ba đường cắt cách mép trái các khoảng $1,3,5$. Nếu JOI-kun cắt tại các đường cắt cách mép trái các khoảng $3,5$, cậu thu được ba miếng. Dãy độ dài các miếng là $(3,2,5)$, là dãy zíc zắc. Vì không thể thu được nhiều hơn ba miếng, hãy xuất $3$.

Dữ liệu vào này thỏa mãn các giới hạn của nhiệm vụ con 1, 2, 3, 5, 6.