همان‌طور که از اسم گروه‌های نظامی پیدا است، نظم یکی از ارکان مهم چنین گروه‌هایی است به طوری که حتی ترتیب قرار گرفتن افراد در صف هم اهمیت دارد. برای ارزیابی نظم یک صف، «نظریه‌ی صف‌ها» مطرح شده که به بعضی از تعاریف آن در ادامه‌ی سوال اشاره شده است.
شما باید با گرفتن دنباله‌ی قد افراد یک صف، به پرسش‌های به شکل «نظام‌مندی زیرصف $[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$ آمده است.