Se dă un șir $a_1, \ldots, a_n$ și $q$ query-uri independente. În cadrul fiecărui query, se dau 2 numere naturale $l$ și $r$. Se consideră secvența $a_l, a_{l+1}, \ldots, a_{r}$. Sarcina ta este să calculezi suma celor mai mici numere excluse ale tuturor secvențelor de forma $a_{i}, a_{i+1}, \ldots, a_{j}$, pentru $l \leq i \leq j \leq r$.

Cel mai mic număr exclus al unei secvențe este cel mai mic număr natural care nu apare în secvență. De exemplu, pentru secvența $0, 1, 4, 2$ acesta este $3$, dar pentru secvența $1, 2, 3, 4$ acesta este $0$.

Date de intrare

Prima linie din input conține numerele $n$ și $q$. A doua linie conține $n$ numere $a_1, a_2, \dots, a_n$, care reprezintă șirul inițial. Fiecare dintre următoarele $q$ linii conține două numere $l$ și $r$, care descriu, în ordine, fiecare query.

Date de ieșire

Output-ul trebuie să conțină răspunsurile celor $q$ query-uri în ordine, fiecare pe câte un rând nou.

Restricții

• $1 \leq n, q \leq 2 \cdot 10^5$
• $0 \leq a_i \leq n$
• $1 \leq l \leq r \leq n$

Subtask 1 (3 puncte)

• $1 \leq a_i \leq n$

Subtask 2 (10 puncte)

• $1 \leq q \leq 200$
• $r - l \leq 200$ pentru fiecare query

Subtask 3 (12 puncte)

• $1 \leq n \leq 5 \ 000$

Subtask 4 (15 puncte)

• Fiecare număr de la $0$ la $n - 1$ apare exact o dată în $a_1, a_2 \dots, a_n$.

Subtask 5 (15 puncte)

• $0 \leq a_i \leq 100$
• Nu există două query-uri $i$ și $j$ astfel încât $l_i < l_j$ și $r_j < r_i$.

Subtask 6 (22 puncte)

• $l = 1$ pentru fiecare query.

Subtask 7 (23 puncte)

• Fără restricții suplimentare.

Exemplu

stdin

6 3
0 1 2 0 1 3
1 2
3 5
1 6

stdout

3
7
39

Explicații

Explicații pentru primele două query-uri:



Explicație pentru al treilea query: