Mizuyokan เป็นขนมญี่ปุ่นที่ทำจากถั่วอะซูกิบด โดยนำถั่วอะซูกิบดไปต้มกับวุ้น แล้วทำให้แข็งตัวในพิมพ์รูปสี่เหลี่ยมผืนผ้า

ขณะนี้ JOI-kun มี เครื่องทำ mizuyokan เครื่องนี้ทำ mizuyokan รูปสี่เหลี่ยมผืนผ้ายาวในแนวนอนที่มีแนวตัดแนวตั้ง $N-1$ แนวได้ ความยาวของขนมและตำแหน่งแนวตัดถูกกำหนดโดยพารามิเตอร์ $N$ ตัว $d_1,d_2,\ldots,d_N$ ที่ตั้งไว้บนเครื่อง ความยาวของขนมคือ $d_1+d_2+\cdots+d_N$ ระยะระหว่างแนวตัดที่ $i-1$ ($1\le i\le N$) จากซ้ายกับแนวตัดที่ $i$ จากซ้ายคือ $d_i$ โดยถือว่าขอบซ้ายสุดของขนมเป็นแนวตัดที่ $0$ และขอบขวาสุดเป็นแนวตัดที่ $N$ เริ่มแรก พารามิเตอร์ของเครื่องเป็นไปตาม $d_i=L_i$ ($1\le i\le N$)

JOI-kun วางแผนจัดงานเลี้ยงน้ำชา $Q$ ครั้ง งานครั้งที่ $j$ ($1\le j\le Q$) อธิบายด้วยจำนวนเต็ม $X_j,Y_j,A_j,B_j$ และดำเนินไปดังนี้

1. ปรับพารามิเตอร์ $d_{X_j}$ ของเครื่องทำ mizuyokan ให้เป็น $Y_j$
2. JOI-kun ใช้เครื่องทำ mizuyokan ชิ้นใหม่ เขานำส่วนระหว่างแนวตัดที่ $A_j$ กับแนวตัดที่ $B_j$ มาใช้ในงานเลี้ยง และกินส่วนที่เหลือเอง
3. JOI-kun ตัดส่วนที่เตรียมไว้สำหรับงานเลี้ยงตามแนวตัดบางแนวให้เป็นอย่างน้อยหนึ่งชิ้น โดยต้องเป็นไปตามเงื่อนไขต่อไปนี้: หากเรียงชิ้นขนมจากซ้ายตามตำแหน่งเดิม ลำดับความยาวของชิ้นขนมต้องเป็นแบบซิกแซก

ลำดับเรียกว่า ซิกแซก หากสมาชิกเพิ่มขึ้นและลดลงสลับกัน ตัวอย่างเช่น ลำดับ $(2,9,2,7)$, $(7,1,9,4,6)$, $(5)$, $(2,1)$ เป็นซิกแซก แต่ลำดับ $(1,2,3)$, $(7,1,4,4,6)$, $(2,2)$ ไม่เป็นซิกแซก กล่าวอย่างแม่นยำ ลำดับ $(x_1,x_2,\ldots,x_m)$ เป็นซิกแซกหากเป็นไปตามเงื่อนไขต่อไปนี้อย่างน้อยหนึ่งข้อ (หรือทั้งสองข้อ)

• สำหรับ $k=1,2,\ldots,m-1$ จะมี $x_k<x_{k+1}$ หาก $k$ เป็นคี่ และ $x_k>x_{k+1}$ หาก $k$ เป็นคู่
• สำหรับ $k=1,2,\ldots,m-1$ จะมี $x_k>x_{k+1}$ หาก $k$ เป็นคี่ และ $x_k<x_{k+1}$ หาก $k$ เป็นคู่

เนื่องจาก JOI-kun ต้องการแบ่ง mizuyokan ให้เพื่อนให้ได้มากคนที่สุด เขาจึงต้องการให้จำนวนชิ้นที่ได้จากขั้นตอนที่ 3 ของงานเลี้ยงมากที่สุด

จงเขียนโปรแกรมที่รับข้อมูลพารามิเตอร์เริ่มต้นของเครื่องทำ mizuyokan และแผนงานเลี้ยงน้ำชา แล้วคำนวณจำนวนชิ้นสูงสุดที่เป็นไปได้ในแต่ละงาน โดยตัดส่วนของขนมให้เป็นไปตามเงื่อนไข โปรดทราบว่าภายใต้ข้อจำกัดของโจทย์นี้ สามารถตัดส่วนของขนมให้เป็นไปตามเงื่อนไขได้เสมอ

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

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

ข้อมูลส่งออก

เขียน $Q$ บรรทัดไปยังข้อมูลส่งออกมาตรฐาน บรรทัดที่ $j$ ($1\le j\le Q$) สอดคล้องกับงานเลี้ยงครั้งที่ $j$ โดยประกอบด้วยจำนวนชิ้นสูงสุดที่ได้จากการตัดส่วนของ mizuyokan ในงานครั้งนั้นให้เป็นไปตามเงื่อนไข

ข้อจำกัด

• $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$)
• ค่าที่กำหนดทั้งหมดเป็นจำนวนเต็ม

งานย่อย

1. (6 คะแนน) $N\le200$, $Q\le10$
2. (9 คะแนน) $N\le2\,000$, $Q\le10$
3. (13 คะแนน) $Q\le10$
4. (32 คะแนน) $Y_j=L_{X_j}$ ($1\le j\le Q$)
5. (29 คะแนน) $L_i\le120\,000$ ($1\le i\le N$), $Y_j\le120\,000$ ($1\le j\le Q$)
6. (11 คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

3

หมายเหตุ

ในงานเลี้ยงครั้งแรก พารามิเตอร์ของเครื่องถูกตั้งเป็น $(d_1,d_2,d_3,d_4,d_5,d_6)=(5,6,8,7,4,9)$ JOI-kun ใช้ส่วนระหว่างแนวตัดที่ $0$ กับแนวตัดที่ $5$ ดังรูปที่ 1

รูปที่ 1. Mizuyokan สำหรับงานเลี้ยงน้ำชา

ตัวอย่างเช่น JOI-kun สามารถตัดส่วนของขนมได้ดังนี้

รูปที่ 2. วิธีตัด mizuyokan สามวิธี จากบนลงล่างคือวิธีที่ 1 วิธีที่ 2 และวิธีที่ 3

ในวิธีที่ 1 ความยาวของแต่ละชิ้นคือ $5,14,7,4$ เนื่องจากลำดับนี้ไม่เป็นซิกแซก จึงไม่เป็นไปตามเงื่อนไข ส่วนวิธีที่ 2 ความยาวของแต่ละชิ้นคือ $11,8,11$ ซึ่งเป็นซิกแซก จึงเป็นไปตามเงื่อนไข ในวิธีที่ 3 ความยาวของชิ้นขนมคือ $30$ ลำดับนี้เป็นซิกแซก จึงเป็นไปตามเงื่อนไขเช่นกัน

หาก JOI-kun ตัดขนมด้วยวิธีที่ 2 จะได้ $3$ ชิ้น เนื่องจากไม่สามารถตัดให้เป็นไปตามเงื่อนไขและได้อย่างน้อย $4$ ชิ้น จึงส่งออก $3$ ในบรรทัดแรก

ข้อมูลนำเข้าตัวอย่างนี้เป็นไปตามข้อจำกัดของงานย่อยทั้งหมด

ข้อมูลนำเข้า 2

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

ข้อมูลส่งออก 2

1
2
3

หมายเหตุ

ในงานเลี้ยงครั้งแรก ส่วนของขนมสำหรับงานเลี้ยงมีความยาว $4$ และมีแนวตัดหนึ่งแนวที่ห่างจากขอบซ้ายสุด $2$ หาก JOI-kun ใช้ขนมโดยไม่ตัด จะได้หนึ่งชิ้น ลำดับความยาวคือ $(4)$ ซึ่งเป็นซิกแซก เนื่องจากไม่สามารถได้มากกว่าหนึ่งชิ้น จึงส่งออก $1$

ในงานเลี้ยงครั้งที่สอง ส่วนของขนมสำหรับงานเลี้ยงมีความยาว $9$ และมีแนวตัดสองแนวที่ห่างจากขอบซ้ายสุด $2,4$ หาก JOI-kun ตัดที่แนวตัดที่ห่างจากขอบซ้ายสุด $4$ จะได้สองชิ้น ลำดับความยาวคือ $(4,5)$ ซึ่งเป็นซิกแซก เนื่องจากไม่สามารถได้มากกว่าสองชิ้น จึงส่งออก $2$

ในงานเลี้ยงครั้งที่สาม ส่วนของขนมสำหรับงานเลี้ยงมีความยาว $10$ และมีแนวตัดสามแนวที่ห่างจากขอบซ้ายสุด $1,3,5$ หาก JOI-kun ตัดที่แนวตัดที่ห่างจากขอบซ้ายสุด $3,5$ จะได้สามชิ้น ลำดับความยาวคือ $(3,2,5)$ ซึ่งเป็นซิกแซก เนื่องจากไม่สามารถได้มากกว่าสามชิ้น จึงส่งออก $3$

ข้อมูลนำเข้าตัวอย่างนี้เป็นไปตามข้อจำกัดของงานย่อย $1,2,3,5,6$