Diferențe pentru problema/calin între reviziile #3 si #2

== include(page="template/taskheader" task_id="calin") ==

*Nota 1*: Problema este adaptată după "Stable Market":https://www.codechef.com/problems/SMARKET (Code Chef).
 
*Nota 2*: Punctajele subtaskurilor au fost modificate.
 

Călin publică un film pe TikTok în care vorbește timp de $n$ minute despre cel mult 9 subiecte. La fiecare minut $i$ ($1 ≤ i ≤ n$) el vorbește despre subiectul $s[~i~]$.
Numim *delir* o subsecvență *maximală* de minute în care Călin vorbește despre același subiect. Numim *delir de gravitate $k$* un delir cu durata de $k$ minute.

h2. Date de intrare

Fișierul de intrare $calin.in$ conține pe prima linie numerele $n$ și $q$, separate prin spațiu. A doua linie conține valorile $s[~1~] s[~2~] ... s[~n~]$, separate prin spații. Fiecare dintre următoarele $q$ linii conține cîte un triplet de numere $l r k$ cu semnificația de mai sus.

Fișierul de intrare $calin.in$ ...

h2. Date de ieșire

În fișierul de ieșire $calin.out$ afișați răspunsurile la interogări, cîte unul pe linie, în aceeași ordine ca la intrare.

În fișierul de ieșire $calin.out$ ...

h2. Restricții

* $1 ≤ n, q ≤ 200.000$
* $1 ≤ s[~i~] ≤ 9$ pentru orice $1 ≤ i ≤ n$
* $1 ≤ l ≤ r ≤ n$ și $1 ≤ k ≤ r − l + 1$ pentru fiecare interogare
 
table{width: inherit}.
|_. subtask |_. puncte |_. restricții |
| 1 | 15 | $n, q ≤ 15.000$ |
| 2 | 55 | $n, q ≤ 80.000$ |
| 3 | 30 | Fără restricții suplimentare. |

* $... ≤ ... ≤ ...$

h2. Exemplu