همان‌طور که از اسم گروه‌های نظامی پیدا است، نظم یکی از ارکان مهم چنین گروه‌هایی است به طوری که حتی ترتیب قرار گرفتن افراد در صف هم اهمیت دارد. برای ارزیابی نظم یک صف، «نظریه‌ی صف‌ها» مطرح شده که به بعضی از تعاریف آن در ادامه‌ی سوال اشاره شده است.

• منظور از زیر صف $[l,r]$ از صف $q$، صفی شامل افراد $l$- ام تا $r$- ام از $q$ با همان ترتیب اولیه است. در واقع زیر صف $[l,r]$، صفی به طول $r-l+1$ است.
• اگر دنباله‌ی قد افراد یک صف (بر حسب نانومتر) را $h_1,h_2,…,h_n$ در نظر بگیرید، رتبه‌ی صف برابر است با طول بزرگ‌ترین (بر حسب الفبایی) زیردنباله‌ی نه لزوما متوالی از دنباله‌ی $h$.
• نظام‌مندی یک صف نیز برابر است با مجموع رتبه‌ی تمامی زیرصف‌های آن. دقت کنید که تعداد زیرصف‌های یک صف به طول $l$ برابر با $\frac{l\times (l+1)}{2}$ است.

شما باید با گرفتن دنباله‌ی قد افراد یک صف، به پرسش‌های به شکل «نظام‌مندی زیرصف $[l,r]$ چقدر است؟» پاسخ دهید.

سطر اول ورودی شامل دو عدد طبیعی $n$، تعداد افراد صف و $k$، تعداد پرسش‌ها، است.($1\leq n,k \leq 3\times 10^5$)

سطر دوم شامل دنباله‌ی $h_1,h_2,…,h_n$ است که قد افراد صف را بر حسب نانومتر نشان می‌دهد.($1\leq h_i \leq 10^9$)

در هر یک از $k$ سطر بعدی به ترتیب دو عدد طبیعی $l$ و $r$ آمده است.($1\leq l \leq r \leq n$)

خروجی باید شامل $k$ سطر باشد که در سطر $i$ ام از آن، پاسخ به پرسش شماره‌ی $i$ آمده است.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل