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.

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 ≤ 200.000
• 1 ≤ Q ≤ 200.000
• Numerele din șirul lui Gigel ≤ 10⁹
• 1 ≤ L ≤ R ≤ N
• 1 ≤ X ≤ 10⁹

Subtaskul 1 (4 puncte)

• 1 ≤ N, Q ≤ 300

Subtaskul 2 (5 puncte)

• 1 ≤ N ≤ 2000
• Toți X sunt egali

Subtaskul 3 (11 puncte)

• 1 ≤ N, Q ≤ 2000

Substaskul 4 (12 puncte)

• 1 ≤ N, Q ≤ 10.000
• Toți X sunt egali

Substaskul 5 (12 puncte)

• 1 ≤ N, Q ≤ 200.000
• Toți X sunt egali

Subtaskul 6 (20 puncte)

• 1 ≤ N, Q ≤ 10.000

Exemplu

Explicaţie

...

Cum se trimit solutii?