Rezolvare PBinfo #3108

Se dau N numere naturale s[1], s[2], …, 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], …, 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[b], cu 1 ≤ a ≤ b ≤ 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, sa1, sa2, …, sak cu 1 ≤ a1 < a2 < ... < ak ≤ 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 ≤ N ≤ 400.000
• 1 ≤ Q ≤ 10.000
• 1 ≤ s[k] ≤ N
• 1 ≤ a ≤ b ≤ 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..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..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..3]=(1 2 3) sunt 1, 2, 3, 1 2, 1 3, 2 3, 1 2 3, deci 7 subșiruri.