Mizuyokan adalah makanan manis Jepang yang terbuat dari pasta kacang azuki. Makanan ini dibuat dengan memasak pasta kacang azuki bersama agar-agar, lalu memadatkannya dalam cetakan berbentuk persegi panjang.

Sekarang, JOI-kun memiliki mesin mizuyokan. Dengan mesin ini, ia dapat membuat mizuyokan berbentuk persegi panjang yang memanjang secara horizontal dengan $N-1$ garis potong vertikal. Panjang mizuyokan dan posisi garis-garis potong ditentukan oleh $N$ parameter $d_1,d_2,\ldots,d_N$ yang diatur pada mesin. Panjang mizuyokan adalah $d_1+d_2+\cdots+d_N$. Jarak antara garis potong ke-$(i-1)$ ($1 \le i \le N$) dari kiri dan garis potong ke-$i$ dari kiri adalah $d_i$. Di sini, tepi paling kiri mizuyokan dianggap sebagai garis potong ke-$0$, dan tepi paling kanannya sebagai garis potong ke-$N$. Pada awalnya, parameter mesin memenuhi $d_i=L_i$ ($1 \le i \le N$).

JOI-kun berencana mengadakan $Q$ jamuan teh. Jamuan teh ke-$j$ ($1 \le j \le Q$) dijelaskan oleh bilangan bulat $X_j,Y_j,A_j,B_j$ dan berlangsung sebagai berikut.

1. Parameter $d_{X_j}$ pada mesin mizuyokan diperbarui menjadi $Y_j$.
2. JOI-kun membuat mizuyokan baru dengan mesin tersebut. Ia mengambil bagian mizuyokan di antara garis potong ke-$A_j$ dan garis potong ke-$B_j$ untuk jamuan teh. Sisanya ia makan.
3. JOI-kun memotong bagian mizuyokan untuk jamuan teh sepanjang sebagian garis potong. Ia membaginya menjadi satu atau lebih potong. Syarat berikut harus dipenuhi: jika potongan diurutkan dari kiri sesuai posisi semula, barisan panjang potongan tersebut harus zigzag.

Suatu barisan disebut zigzag jika elemennya naik dan turun secara bergantian. Sebagai contoh, barisan $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$, $(2,1)$ adalah zigzag, tetapi barisan $(1,2,3)$, $(7,1,4,4,6)$, $(2,2)$ bukan zigzag. Secara tepat, suatu barisan $(x_1,x_2,\ldots,x_m)$ disebut zigzag jika salah satu (atau kedua) syarat berikut dipenuhi:

• Untuk $k=1,2,\ldots,m-1$, berlaku $x_k<x_{k+1}$ jika $k$ ganjil, dan $x_k>x_{k+1}$ jika $k$ genap.
• Untuk $k=1,2,\ldots,m-1$, berlaku $x_k>x_{k+1}$ jika $k$ ganjil, dan $x_k<x_{k+1}$ jika $k$ genap.

Karena JOI-kun ingin memberikan mizuyokan kepada sebanyak mungkin teman, ia ingin memaksimalkan jumlah potongan yang diperoleh pada langkah 3 jamuan teh.

Diberikan informasi parameter awal mesin mizuyokan dan rencana jamuan teh, tulislah program yang menghitung, untuk setiap jamuan teh, jumlah maksimum potongan yang dapat diperoleh dengan memotong bagian mizuyokan sehingga syarat tersebut dipenuhi. Perhatikan bahwa, dalam batasan soal ini, selalu mungkin memotong bagian mizuyokan sehingga syarat tersebut dipenuhi.

Masukan

Baca data berikut dari masukan standar.

$$ \begin{gathered} 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{gathered} $$

Keluaran

Tuliskan $Q$ baris ke keluaran standar. Baris ke-$j$ ($1 \le j \le Q$) berkaitan dengan jamuan teh ke-$j$. Baris tersebut berisi jumlah maksimum potongan yang dapat diperoleh dengan memotong bagian mizuyokan pada jamuan teh ke-$j$ sehingga syarat tersebut dipenuhi.

Batasan

• $1 \le N \le 250\,000$.
• $1 \le L_i \le 10^9$ ($1 \le i \le N$).
• $1 \le Q \le 50\,000$.
• $1 \le X_j \le N$ ($1 \le j \le Q$).
• $1 \le Y_j \le 10^9$ ($1 \le j \le Q$).
• $0 \le A_j<B_j \le N$ ($1 \le j \le Q$).
• Semua nilai yang diberikan adalah bilangan bulat.

Subsoal

1. (6 poin) $N \le 200$, $Q \le 10$.
2. (9 poin) $N \le 2\,000$, $Q \le 10$.
3. (13 poin) $Q \le 10$.
4. (32 poin) $Y_j=L_{X_j}$ ($1 \le j \le Q$).
5. (29 poin) $L_i \le 120\,000$ ($1 \le i \le N$), $Y_j \le 120\,000$ ($1 \le j \le Q$).
6. (11 poin) Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

3

Penjelasan

Pada jamuan teh pertama, parameter mesin mizuyokan diatur menjadi $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$. JOI-kun menggunakan bagian mizuyokan di antara garis potong ke-$0$ dan garis potong ke-$5$, seperti pada Gambar 1.

Gambar 1. Mizuyokan untuk jamuan teh

Sebagai contoh, JOI-kun dapat memotong bagian mizuyokan sebagai berikut.

Gambar 2. Tiga cara memotong mizuyokan. Dari atas: Cara 1, Cara 2, Cara 3.

Pada Cara 1, panjang potongan adalah $5,14,7,4$. Karena barisan ini bukan zigzag, syarat tidak dipenuhi. Sebaliknya, pada Cara 2, panjang potongan adalah $11,8,11$. Karena barisan ini zigzag, syarat dipenuhi. Pada Cara 3, panjang potongan adalah $30$. Karena barisan ini zigzag, cara tersebut juga memenuhi syarat.

Jika JOI-kun memotong bagian mizuyokan dengan Cara 2, ia memperoleh $3$ potong. Karena tidak mungkin memotongnya agar syarat dipenuhi dan memperoleh setidaknya $4$ potong, keluarkan $3$ pada baris pertama.

Contoh masukan ini memenuhi batasan semua subsoal.

Masukan 2

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

Keluaran 2

1
2
3

Penjelasan

Pada jamuan teh pertama, panjang bagian mizuyokan untuk jamuan adalah $4$. Ada satu garis potong yang berjarak $2$ dari tepi paling kiri. Jika JOI-kun menggunakan mizuyokan tanpa memotongnya, ia memperoleh satu potong. Barisan panjang potongannya adalah $(4)$, yang merupakan zigzag. Karena ia tidak dapat memperoleh lebih dari satu potong, keluarkan $1$.

Pada jamuan teh kedua, panjang bagian mizuyokan untuk jamuan adalah $9$. Ada dua garis potong yang berjarak $2,4$ dari tepi paling kiri. Jika JOI-kun memotong mizuyokan pada garis potong yang berjarak $4$ dari tepi paling kiri, ia memperoleh dua potong. Barisan panjang potongannya adalah $(4,5)$, yang merupakan zigzag. Karena ia tidak dapat memperoleh lebih dari dua potong, keluarkan $2$.

Pada jamuan teh ketiga, panjang bagian mizuyokan untuk jamuan adalah $10$. Ada tiga garis potong yang berjarak $1,3,5$ dari tepi paling kiri. Jika JOI-kun memotong mizuyokan pada garis-garis potong yang berjarak $3,5$ dari tepi paling kiri, ia memperoleh tiga potong. Barisan panjang potongannya adalah $(3,2,5)$, yang merupakan zigzag. Karena ia tidak dapat memperoleh lebih dari tiga potong, keluarkan $3$.

Contoh masukan ini memenuhi batasan Subsoal $1,2,3,5,6$.