macseq

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.
 

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*.

* 1 ≤ *N*, *Q* ≤ 300

h3. Subtaskul 2 (10 puncte)

h3. Subtaskul 2 (12 puncte)

* 1 ≤ *N* ≤ 5000
* Toate *X*-urile sunt sunt egale

h3. Subtaskul 3 (14 puncte)

h3. Subtaskul 3 (16 puncte)

* 1 ≤ *N*, *Q* ≤ 2000