====== بریم مصر (Let's go to Egypt) ======

پس از اینکه روابط ایران و مصر بهبود یافت، سه نفر از ایرانیان توانستند ویزای مصر را اخذ کنند. آنها پس از رسیدن به مصر، قصد دارند که اول از خیابان معروف "طلعت حرب" دیدن کنند. در این خیابان 
$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$



===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
| <code>
5
5 4 1 3 2
5
1 5
2 5
2 4
1 3
1 2
</code> | <code>
11 9 6 5 3
</code> |
| <code>
9
5 2 3 3 6 4 6 4 1
5
1 9
4 9
3 8
2 5
7 8
</code> | <code>
29 15 18 10 3
</code> |
</WRAP>

===== شرح ورودی و خروجی نمونه =====

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



<span hi>
سعی کنید سوالات را با کمترین راهنمایی از بالا به پایین حل کنید.
</span>

<راهنمایی>
شرط لازم و کافی برای قابل بازدید بودن یک بازه، چنین است که طول بلندترین زیردنباله نزولی (نه لزوما اکید) این بازه حداکثر ۲ باشد.
</راهنمایی>


<راهنمایی>
به ازای هر ساختمان مانند $i$، کوچکترین $l$ را به دست می‌آوریم که بازه‌ی $[l, i]$ شرط راهنمایی ۱ را داشته باشند. این مقدار را $left[i]$ می نامیم. در این صورت تمام بازه‌های $[j , i]$ به طوری که  $l \le i \le r$ نیز شرط راهنمایی ۱ را دارند.
</راهنمایی>


<راهنمایی>
جواب مسئله برای پرسش $[l,r]$ برابر با مجموع $(i - left[i] + 1)$ به ازای تمام $l \le i \le r$ است.
</راهنمایی>

<راهنمایی>
دفت کنید که آرایه‌ی $left[i]$ ها صعودی است.
</راهنمایی>

<راهنمایی>
 با استفاده از الگوریتم‌های جست‌ و جوی دودویی و جمع پیشوندی $(prefix \> sum)$ می‌توان مقدار گفته شده در راهنمایی ۳ را در $O(\log{n})$ محاسبه کرد.
</راهنمایی>

  * [[سوال ۲|سوال بعد]]