• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• آزمون عملی سوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران

---

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

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

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

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

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

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

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

ورودی

در خط اول ورودی، $n$ یا همان تعداد ساختمان ها می‌آید. $$1 \leq n \leq 500 , 000$$

در خط دوم ورودی، $n$ عدد صحیح می آیند که عدد $i$ ام همان $a_i$ است. $$0 \leq a_i \leq 10^ 9$$

در خط سوم ورودی، $Q$ یا همان تعداد تاکسی ها می‌آید. $$1 \leq Q \leq 500 , 000$$

در $Q$ خط بعدی در هر خط دو عدد $r_i$ و $l_i$ به ترتیب می‌آیند. $$1 \leq l_i \leq r_i \leq n$$

خروجی

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

زیرمسئله‌ها

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

مثال‌ها

ورودی نمونه ۱

5
5 4 1 3 2
5
1 5
2 5
2 4
1 3
1 2

خروجی نمونه ۱

11 9 6 5 3

ورودی نمونه ۲

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

خروجی نمونه ۲

29 15 18 10 3

در ورودی نمونه اول به ازای تاکسی دوم، تعداد کل حالت‌هایی که می‌توانند از تعدادی ساختمان متوالی بازدید بکنند برابر $10$ است. از بین این $10$ حالت، حالتی که از کل ساختمان‌های بازه $[2, 5]$ بازدید بکنند خوشایند نیست؛ زیرا نفر اول و دوم راضی به بازدید از ساختمان با زیبایی $3$ نیستند.