Această problemă se numește Calafat pentru că a fost compusă în timpul excursiei la Calafat de mâine.
Cerință
Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între 2 indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st, dr], se cere să se calculeze suma distanțelor corespunzătoare tuturor valorilor distincte din subsecvență.
Date de intrare
Pe prima linie a fișierului de intrare calafat.in se vor afla două numere natural N și M. Pe a doua linie se vor afla cele N numere din sirul dat. Pe următoarele M linii se vor afla câte două numere st și dr, cu semnificația că vrem să calculăm suma menționată mai sus pentru subsecvența [st, dr].
Date de ieșire
În fișierul de ieșire calafat.out se vor afișa M numere naturale, câte unul pe fiecare linie, reprezentând cele M sume cerute.
Restricții și precizări
1 ≤ N, M ≤ 200 0001 ≤ st ≤ dr ≤ N- Valorile din șir se vor afla în intervalul
[1, N] - Pentru
20%din teste se garantează căN, M ≤ 1000 - Pentru alte
25%din teste se garantează căN, M ≤ 35 000iar numărul de elemente distincte din șir este maxim100. - Pentru alte
25%din teste se garantează căN, M ≤ 70 000
Exemplu
calafat.in
7 3
1 3 1 2 2 1 3
2 4
2 7
3 6
calafat.out
0
9
4
Explicaţii
În prima subsecvență fiecare valoare apare o singură dată, deci suma diferențelor este 0.
În a doua subsecvență: Valoarea 3 apare la indicii 2 și 7 rezultând diferența 7-2=5 Valoarea 1 apare la indicii 3 și 6 => diferența 6–3=3
Valoarea 2 apare la indicii 4 și 5 => diferența 5-4=1
Suma diferențelor este 9.
În a treia subsecvență: Valoarea 1 apare la indicii 3 și 6 => diferența 6–3=3
Valoarea 2 apare la indicii 4 și 5 => diferența 5-4=1
Suma diferențelor este 4.