معظم سطح كوكب فضائي صحراء، ولذلك نادرًا ما تمطر عليه. جميع نباتاته صبار. ولأن المطر نادر جدًا، تطورت لدى نباتات الصبار طريقة للتعاون على تخزين الماء.

إحدى مناطق الكوكب مستوى ثنائي الأبعاد لا توجد فيه إلا اتجاهات أعلى-أسفل ويسار-يمين. تقف في هذه المنطقة $N$ نباتات صبار متلاصقة في صف واحد. عرض كل نبتة $1$ متر، وقد تختلف ارتفاعاتها. لتجميل البيئة، تُترك فقط نباتات الصبار من $S$ إلى $E$. ثم يهطل مطر كافٍ لملء كل المناطق فوق الصبار التي يمكنها الاحتفاظ بالماء. يتجمع الماء كما في الشكل أدناه. اعتبر نباتات الصبار خارج النطاق المحدد بالأسهم محذوفة.

اكتب برنامجًا يأخذ ارتفاعات الصبار ونطاق النباتات المتبقية، ويحسب كمية الماء المحتجز على شكل مساحة. يُعطى ما لا يزيد على $Q$ نطاقات. يُطبّق كل نطاق دائمًا على الحالة الابتدائية التي توجد فيها جميع نباتات الصبار.

يجب تنفيذ الدوال التالية.

• void init( int H[] ): تُستدعى مرة واحدة فقط في البداية. $H$ مصفوفة (متجه) بحجم $N$ تحتوي ارتفاعات الصبار بالترتيب من اليسار إلى اليمين. $N$ هو عدد نباتات الصبار.
• int query( int S, int E ): أعد مساحة الماء المحتجز بعد هطول مطر كافٍ عندما تبقى فقط نباتات الصبار من $S$ إلى $E$ ($1 \le S \le E \le N$). تُستدعى هذه الدالة ما لا يزيد على $Q$ مرات. جميع الاستدعاءات مستقلة: حذف الصبار في استدعاء لا يؤثر على غيره.

تفاصيل التنفيذ

يجب إرسال ملف واحد بالضبط باسم cactus.cpp. يجب أن ينفذ هذا الملف الدوال التالية.

• void init( int H[] )
• long long query( int S, int E )

يجب أن تعمل الدوال كما وُصف أعلاه. يمكنك تعريف دوال أخرى للاستخدام الداخلي. يجب ألا ينفذ الكود المرسل أي إدخال أو إخراج وألا يصل إلى ملفات أخرى.

نموذج برنامج التقييم

يقرأ برنامج التقييم المرفق الإدخال بالتنسيق التالي.

• السطر 1: $N$ و$Q$.
• السطر التالي: $N$ أعداد صحيحة موجبة، هي ارتفاعات الصبار من اليسار إلى اليمين.
• الأسطر الـ $Q$ التالية: عددان صحيحان موجبان $S,E$، يعنيان أن المطر يهطل مع بقاء نباتات الصبار من $S$ إلى $E$ فقط ($1 \le S \le E \le N$).

يطبع برنامج التقييم المرفق القيم التي تعيدها دالتك query()، قيمة واحدة في كل سطر.

القيود

• $1 \le N \le 500\,000$ و$1 \le Q \le 500\,000$؛ ارتفاع كل نبتة صبار لا يقل عن $1$ ولا يزيد على $10^9$.

المهام الفرعية

المهام الفرعية 1 (13 نقطة)

• $1 \le N \le 5\,000$, $1 \le Q \le 5\,000$

المهام الفرعية 2 (12 نقطة)

• $1 \le N \le 5\,000$

المهام الفرعية 3 (22 نقطة)

• ارتفاع كل نبتة صبار لا يزيد على $20$.

المهام الفرعية 4 (34 نقطة)

• $1 \le N \le 100\,000$, $1 \le Q \le 100\,000$

المهام الفرعية 5 (69 نقطة)

• لا توجد قيود إضافية غير القيود الأصلية.

أمثلة

الإدخال 1

10 3
1 3 2 5 1 4 6 2 1 3
2 8
2 4
7 9

ملاحظة

يوضح ما يلي مثالًا لتنفيذ كودك على الإدخال أعلاه.