== include(page="template/taskheader" task_id="macseq") ==
Gigel are un șir de *N* numere naturale. Acesta vă cere ajutorul în rezolvarea a *Q* interogări de forma *L*, *R*, *X*. Pentru fiecare întrebare Gigel vrea să știe numarul de subsecvențe care sunt incluse in intervalul [*L*, *R*] și au maximul egal cu *X*.
O subsecvență este o submulțime de elemente ale șirului aflate pe poziții consecutive.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $macseq.in$ conține pe prima linie *N* și *Q* cu semnificațiile din enunț. Următoarea linie conține șirul lui Gigel. Pe următoarele *Q* linii sunt prezentate interogările de forma *L*, *R*, *X*.
Fişierul de intrare $macseq.in$ ...
h2. Date de ieşire
În fişierul de ieşire $macseq.out$ trebuie sa afișați pe fiecare linie separat raspunusul la întrebările lui Gigel.
În fişierul de ieşire $macseq.out$ ...
h2. Restricţii
* 1 ≤ *N*, *Q* ≤ 200.000
* 1 ≤ *L* ≤ *R* ≤ *N*
* 1 ≤ *X*, Numerele din șirul lui Gigel ≤ 10^9^
h3. Subtaskul 1 (6 puncte)
* 1 ≤ *N*, *Q* ≤ 300
h3. Subtaskul 2 (12 puncte)
* 1 ≤ *N* ≤ 5000
* Toate *X*-urile sunt sunt egale
h3. Subtaskul 3 (16 puncte)
* 1 ≤ *N*, *Q* ≤ 2000
h3. Substaskul 4 (22 puncte)
* 1 ≤ *N*, *Q* ≤ 200.000
* Toate *X*-urile sunt sunt egale
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. macseq.in |_. macseq.out |
|6 3
15 33 55 33 12 46
1 6 33
2 4 33
1 6 55
|4
2
12
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Subsecvențele care indeplinesc condițiile la prima interogare sunt [2,2], [1,2], [4,4], [4,5]. La a 2-a sunt [2,2] si [4,4].
...
== include(page="template/taskfooter" task_id="macseq") ==
