dss

Se dau $N$ numere naturale $s_1$, $s_2$, $\dots$, $s_N$ și $Q$ interogări de forma $a \ b$.

Cerința

Să se determine pentru fiecare interogare $[a; b]$ numărul de subșiruri formate din elemente distincte ale secvenței $s_a$, $s_{a+1}$, $s_{a+2}$, $\dots$, $s_b$. Prin secvență a șirului $s$ se înțelege orice succesiune de elemente aflate pe poziții consecutive $s_a$, $s_{a+1}$, $s_{a+2}$, $\dots$, $s_b$, cu $1 \leq a \leq b \leq N$.

Prin subșir al șirului $s$ se înțelege orice succesiune de elemente aflate pe poziții în ordine strict crescătoare, dar nu neapărat consecutive, $s_{a_1}$, $s_{a_2}$, $\dots$, $s_{a_k}$ cu $1 \leq a_1 < a_2 < \dots < a_k \leq N$.

Date de intrare

Fișierul de intrare dss.in conține pe primul rând numerele $N$ și $Q$. Pe linia a doua sunt scrise $N$ numere naturale separate prin câte un spațiu. Pe următoarele $Q$ rânduri sunt scrise câte două numere naturale $a \ b$, separate prin spațiu, reprezentând capetele intervalelor de interogare date.

Date de ieșire

În fișierul de ieșire dss.out pe fiecare dintre primele $Q$ rânduri este scris câte un număr natural reprezentând numărul tuturor subșirurilor formate din elemente distincte conținute în secvența din interogarea corespunzătoare.

Restricții și precizări

• $1 \leq N \leq 400 \ 000$
• $1 \leq Q \leq 10 \ 000$
• $1 \leq s_k \leq N$
• $1 \leq a \leq b \leq N$
• Numărul de subșiruri pentru fiecare interogare vor fi calculate modulo $1 \ 000 \ 000 \ 007$

Exemplu

dss.in

5 3 
1 2 3 2 3
1 4
2 5
1 3

dss.out

11
8
7

Explicație

• Subșirurile formate din elemente distincte din secvența $s[1 \dots 4$] = ($1 \ 2 \ 3 \ 2$) sunt $1$, $2$, $3$, $2$, $1 \ 2$, $1 \ 3$, $1 \ 2$, $2 \ 3$, $3 \ 2$, $1 \ 2 \ 3$, $1 \ 3 \ 2$, deci în total $11$ subșiruri.
• Subșirurile formate din elemente distincte din secvența $s[2 \dots 5$] = ($2 \ 3 \ 2 \ 3$) sunt $2$, $3$, $2$, $3$, $2 \ 3$, $2 \ 3$, $3 \ 2$, $2 \ 3$, deci $8$ subșiruri.
• Subșirurile formate din elemente distincte din secvența $s[1 \dots 3$] = ($1 \ 2 \ 3$) sunt $1$, $2$, $3$, $1 \ 2$, $1 \ 3$, $2 \ 3$, $1 \ 2 \ 3$, deci $7$ subșiruri.