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

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

h2. Date de intrare

h2. Restricţii

* 1 ≤ *N* ≤ 200.000
* 1 ≤ *Q* ≤ 200.000
* Numerele din șirul lui Gigel ≤ 10^9^

* 1 ≤ *N*, *Q* ≤ 200.000

* 1 ≤ *L* ≤ *R* ≤ *N*

* 1 ≤ *X* ≤ 10^9^

* 1 ≤ *X*, Numerele din șirul lui Gigel ≤ 10^9^

h3. Subtaskul 1 (6 puncte)

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

|6 3
15 33 55 33 12 46
1 6 33
2 4 33
1 6 55
|4
2
12

|
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") ==