Študenti žijúci na intráku neznášajú komplikované recepty, a aj tie jednoduché sa v ich kuchynkách ťažko varia. Zohnať panvicu môže byť niekedy problém a odniesť všetko náčinie do kuchynky tiež nie je jednoduché. Preto bola pre nich vydaná Kniha jednoduchých receptov, kde každý recept je len zoznam prísad, ktoré sa nahádžu do nádoby (v poradí, v akom sú zadané) a upečú.
Recept môže vyzerať napríklad takto: "zemiak zemiak cesnak vajce zemiak vajce múka korenie zemiak múka". Každá prísada na svete má svoje jedinečné číslo (ľubovoľné prirodzené číslo), takže namiesto predošlého popisu receptu stačí napísať napríklad "3 3 9 1 3 1 7 8 3 4". (Zemiak má v tomto prípade číslo 3, vajce číslo 1, ...) Navyše prísada s číslom $x$ dodá jedlu jednotku magickej chuti práve vtedy, keď sa v jedle nachádza $x$-krát. Magická chuť jedla (nezáporné celé číslo) je teda rovná počtu rôznych čísel $x$ takých, že prísada $x$ je v jedle práve $x$-krát.
Jediná nevýhoda knihy je, že jej autori zabudli jednotlivé recepty od seba oddeliť. Celá kniha je teda len zoznam prísad a nikto nevie, kde sú hranice medzi receptami.
Intrákisti sa však nevzdali a rozhodli sa, že skúsia zistiť, ktoré úseky pravdepodobne tvorili recept. Zisťovať to budú tak, že skúsia vybrať niekoľko súvislých úsekov knihy a spýtajú sa vás, akú magickú chuť majú. Podľa vašich odpovedí potom rozdelia knihu na recepty.
Na vstupe dostanete knihu receptov, v ktorej je zaradom zapísaných $n$ čísel prísad. Následne dostanete $q$ otázok typu: aká je magická chuť jedla, ktoré by vzniklo z nejakého konkrétneho úseku knihy.
Prvý riadok vstupu obsahuje čísla $n$ a $q$ ($1 \leq n,q \leq 400\,000$). Na druhom riadku je zoznam $n$ celých čísel z rozsahu $1$ až $10^9$ vrátane, ktoré tvoria Knihu jednoduchých receptov. Na nasledujúcich $q$ riadkoch je popis otázok. Presnejšie na ($i+2$)-hom riadku ($1\leq i\leq q$) sú čísla $a_i$, $b_i$ ($1\leq a_i\leq b_i \leq n)$, ktoré znamenajú, že sa pýtame na súvislý úsek prísad od $a_i$-tej po $b_i$-tu vrátane.
Pre každú otázku vypíšte, aká je magická chuť daného úseku, teda koľko je v úseku takých čísel $x$, že sa tam vyskytujú práve $x$-krát.
10 3
3 3 9 1 3 1 7 8 3 4
1 5
5 8
4 4
2
1
1