מיזויוקן הוא ממתק יפני העשוי ממחית שעועית אזוקי. מכינים אותו באמצעות בישול המחית עם אגר וקרישתה בתבנית מלבנית.

כעת ל־JOI-kun יש מכונת מיזויוקן. בעזרתה הוא יכול להכין מיזויוקן מלבני המוארך בכיוון האופקי, ובו $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}$ של מכונת המיזויוקן לערך $Y_j$.
2. JOI-kun מכין מיזויוקן חדש באמצעות המכונה. הוא לוקח את החלק שבין קו החיתוך ה־$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$, אם $k$ אי־זוגי מתקיים $x_k<x_{k+1}$, ואם $k$ זוגי מתקיים $x_k>x_{k+1}$.
• לכל $k=1,2,\ldots,m-1$, אם $k$ אי־זוגי מתקיים $x_k>x_{k+1}$, ואם $k$ זוגי מתקיים $x_k<x_{k+1}$.

מכיוון ש־JOI-kun רוצה לתת מיזויוקן לכמה שיותר חברים, הוא מעוניין למקסם את מספר החתיכות המתקבל בשלב 3 של מסיבת התה.

כתבו תוכנית אשר, בהינתן הפרמטרים ההתחלתיים של מכונת המיזויוקן ותוכנית מסיבות התה, מחשבת עבור כל מסיבה את מספר החתיכות המרבי שאפשר לקבל מחיתוך החלק של המיזויוקן כך שהתנאי יתקיים. שימו לב שתחת מגבלות משימה זו תמיד אפשר לחתוך את החלק כך שהתנאי יתקיים.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

$$ \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} $$

פלט

כתבו $Q$ שורות לפלט הסטנדרטי. השורה ה־$j$ ($1 \le j \le Q$) מתאימה למסיבת התה ה־$j$. היא מכילה את מספר החתיכות המרבי שאפשר לקבל מחיתוך חלק המיזויוקן במסיבה זו כך שהתנאי יתקיים.

מגבלות

• $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$).
• כל הערכים הנתונים הם מספרים שלמים.

תת־משימות

1. (6 נקודות) $N \le 200$, $Q \le 10$.
2. (9 נקודות) $N \le 2\,000$, $Q \le 10$.
3. (13 נקודות) $Q \le 10$.
4. (32 נקודות) $Y_j=L_{X_j}$ ($1 \le j \le Q$).
5. (29 נקודות) $L_i \le 120\,000$ ($1 \le i \le N$), $Y_j \le 120\,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. המיזויוקן למסיבת התה

לדוגמה, JOI-kun יכול לחתוך את החלק של המיזויוקן באופן הבא.

איור 2. שלוש שיטות לחיתוך המיזויוקן. מלמעלה למטה: שיטה 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.