Fişierul intrare/ieşire:	macseq.in, macseq.out	Sursă	Baraj Shumen Juniori ICHB-Vianu - 2022
Autor	Armin Asgari, Ilie Luca Mihai	Adăugată de	Comisie Juniori Vianu - ICHB •comisie_baraj_shumen_ichb_vianu_juniori
Timp execuţie pe test	0.3 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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.

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.

Restricţii

• 1 ≤ N, Q ≤ 200.000
• 1 ≤ L ≤ R ≤ N
• 1 ≤ X, Numerele din șirul lui Gigel ≤ 10⁹

Subtaskul 1 (6 puncte)

• 1 ≤ N, Q ≤ 300

Subtaskul 2 (12 puncte)

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

Subtaskul 3 (16 puncte)

• 1 ≤ N, Q ≤ 2000

Substaskul 4 (22 puncte)

• 1 ≤ N, Q ≤ 200.000
• Toate X-urile sunt sunt egale

Exemplu

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

Cum se trimit solutii?