وارونگی در یک بخش
Problem
با توجه به جایگشت n عنصر.
به m پرس و جوها درباره تعداد وارونگی یک زیربخش جایگشتی از l به r پاسخ دهید.
وارونگی یک جفت شاخص i, j است به طوری که i < j و a
i > a
j، که در آن a
i iمین عنصر جایگشت است.
ورودی:
خط اول حاوی عدد n است (1 <= n <= 10
5).
خط دوم شامل یک جایگشت از n عنصر است (عناصر جایگشت اعداد صحیح متمایز زوجی از 1 تا n هستند).
خط سوم حاوی عدد m است (1 <= m <= 10
5).
خطوط m بعدی شامل دو عدد صحیح l و r هستند - کرانهای پرس و جو (1 <= l, r <= n).
خروجی:
m خطوط را چاپ کنید - پاسخ به این سوالات.
مثال:
<بدن>
| ورودی |
خروجی |
5
4 5 2 3 1
3
1 3
3 5
15 |
2
2
8 |
6
5 2 4 3 1 6
3
46
25
15 |
1
4
8 |