Mizuyokan حلوى يابانية تُصنع من معجون فاصولياء azuki. وتُحضَّر بطهي معجون فاصولياء azuki مع الآغار، ثم ترك الخليط يتماسك في قالب مستطيل الشكل.

لدى JOI-kun الآن آلة لصنع mizuyokan. وباستخدامها، يستطيع JOI-kun صنع قطعة mizuyokan مستطيلة طويلة أفقيًا، عليها $N-1$ خط قطع رأسيًا. يتحدد طول القطعة ومواضع خطوط القطع بواسطة المعاملات الـ $N$ المضبوطة على الآلة، وهي $d_1,d_2,\ldots,d_N$. طول القطعة هو $d_1+d_2+\cdots+d_N$. والمسافة بين خط القطع رقم $i-1$ من اليسار وخط القطع رقم $i$ من اليسار هي $d_i$، حيث $1\le i\le N$. ونعدّ الحافة اليسرى للقطعة خط القطع رقم $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$. ويحتوي على أكبر عدد ممكن من القطع الناتجة عن تقطيع الجزء المخصص لحفلة الشاي رقم $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

ملاحظة

في حفلة الشاي الأولى، تُضبط معاملات آلة صنع mizuyokan على $(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 تقطيع جزء mizuyokan كما يلي.

الشكل 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.