پس از اینکه روابط ایران و مصر بهبود یافت، سه نفر از ایرانیان توانستند ویزای مصر را اخذ کنند. آن‌ها پس از رسیدن به مصر، قصد دارند که اول از خیابان معروف "طلعت حرب" دیدن کنند. در این خیابان $n$ ساختمان وجود دارد که در یک خط صاف قرار دارند و به ترتیب از چپ به راست از $1$ تا $n$ شماره‌گذاری شده‌اند. همجنین زیبایی ساختمان $i$م برابر $a_i$ است.

حال در فرودگاه $Q$ تاکسی موجود است. تاکسی شماره $i$ آن سه نفر را در فرودگاه سوار کرده و مقابل ساختمان $l_i$ پیاده می‌کند و سپس در مقابل ساختمان $r_i$ منتظر می‌ماند تا آن‌ها را سوار کرده و به سمت هتل ببرد. ($l_i \leq r_i$) آن‌ها اگر تاکسی شماره $i$ را انتخاب کنند، پس از پیاده شدن از تاکسی همواره به سمت راست می‌روند تا به ساختمان $r_i$ برسند و آنجا سوار تاکسی شوند.

آن‌ها قصد دارند از تعدادی (حداقل یک) ساختمان بازدید کنند به طوری که ساختمان‌های بازدید شده متوالی باشند. توجه کنید در حالت عادی فقط از مقابل ساختمان رد میشوند و لزوما از هر ساختمانی که از رو به روی آن گذر میکنند بازدید نمی‌کنند.

• نفر اول در صورتی از دیدن یک ساختمان راضی است که زیبایی آن از تمام ساختمان‌های قبلی بازدید شده اکیدا بیشتر باشد.
• نفر دوم نیز در صورتی از دیدن یک ساختمان راضی است که زیبایی آن ساختمان از تمام ساختمان‌هایی که در ادامه از آن‌ها بازدید می‌کنند، اکیدا کمتر باشد.
• نفر سوم نیز چون از دو نفر دیگر پیرتر است، سلیقه‌ی عجیبی ندارد و از دیدن تمامی ساختمان‌ها راضی است.

بازدید از یک ساختمان در صورتی برای آن‌ها خوشایند است که اکثریت آن‌ها (حداقل دو نفر) راضی به بازدید از آن ساختمان باشند.

آن‌ها به ازای هر کدام از تاکسی‌ها می‌خواهند بدانند که به چند طریق می‌توانند تعدادی از ساختمان‌هایی که از رو به روی آن‌ها گذر می‌کنند را انتخاب کنند و از آن‌ها بازدید کنند. توجه کنید که آن‌ها از ساختمان های $l_i$ و $r_i$ نیز می‌توانند بازدید کنند. به عبارت دیگر آن‌ها از ساختمان‌های یک زیر بازه از بازه‌ی $\left[l_i, r_i\right]$ بازدید می‌کنند.

همچنین نفر سوم به عنوان پیرترین نفر جمع به شما توصیه می‌کند که برای فهم بهتر سوال به نمونه ورودی ها توجه کنید.

در خط اول $n$ یا همان تعداد ساختمان‌ها می‌آید.

در خط دوم $n$ عدد صحیح می‌آیند که عدد $i$م همان $a_i$ است.

در خط سوم $Q$ یا همان تعداد تاکسی‌ها می‌آید.

در $Q$ خط بعدی در هر خط دو عدد $l_i, r_i$ به ترتیب می‌آیند.

در تنها خط خروجی $Q$ عدد چاپ کنید که عدد $i$م تعداد حالت‌های بازدید کردن آن‌ها در صورت استفاده از تاکسی $i$م است.

• زیرمسئله اول (۹ نمره): $n \leq 500$.
• زیرمسئله دوم (۱۶ نمره): $n \leq 5000$.
• زیرمسئله سوم (۳۶ نمره): $n \leq 10^5, Q \leq 3000$.
• زیرمسئله چهارم (۳۹ نمره): بدون محدودیت اضافی

• $1 \leq n \leq 5 \times 10^5$
• $0 \leq a_i \leq 10^9$
• $1 \leq l_i \leq r_i \leq n$

در ورودی نمونه اول به ازای تاکسی دوم، تعداد کل حالت‌هایی که میتوانند از تعدادی ساختمان متوالی بازدید بکنند برابر ۱۰ است. از بین این ۱۰ حالت، حالتی که از کل ساحتمان‌‌های بازه $\left[2, 5\right]$ بازدید بکنند خوشایند نیست؛ زیرا نفر اول و دوم راضی به بازدید از ساختمان با زیبایی ۳ نیستد.‌

سعی کنید سوالات را با کمترین راهنمایی از بالا به پایین حل کنید.