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