cibernetica

În Imperiul Rațelor de Cauciuc, toate datele importante au fost migrate pe un server central. Mugurel, proaspăt numit Șef al Securității Cibernetice, are ca sarcină monitorizarea rețelei împotriva atacurilor informatice.

Traficul de pe server este înregistrat sub forma unui șir $a$ de $N$ adrese IP de la care au fost efectuate cereri. Fiecare adresă IP din șir este reprezentată simplificat printr-un singur număr natural $a_i$ ($1 \le i \le N$), și două adrese IP diferite sunt reprezentate prin numere diferite.

Pentru a detecta anomalii, Mugurel analizează mai multe ferestre de trafic. O fereastră de trafic este definită de o pereche de indici $(i, j)$, $1 \le i \le j \le N$ și este reprezentată de secvența de IP-uri $[a_i, a_{i+1}, \ldots, a_j]$.

Pentru a evalua starea rețelei, Mugurel folosește un parametru de siguranță $K$ și clasifică ferestrele de trafic astfel:

• o fereastră este considerată suspectă dacă cel puțin o aceeași adresă IP apare în ea de cel puțin $K$ ori;
• o fereastră este considerată legitimă dacă în interiorul ei apar cel puțin $K$ adrese IP distincte.

Cerință

Ajutați-l pe Mugurel să determine, în funcție de o valoare $C$, numărul de ferestre suspecte (dacă $C = 1$) sau numărul de ferestre legitime (dacă $C = 2$) care există în șirul de cereri.

Date de intrare

Fișierul de intrare cibernetica.in conține:

• pe prima linie un număr natural $C$, reprezentând tipul ferestrelor de numărat ($1$ sau $2$);
• pe a doua linie două numere naturale $N$ și $K$, reprezentând numărul adreselor IP, și parametrul de siguranță;
• pe a treia linie $N$ numere naturale, reprezentând, în ordinea cererilor, valorile $a_i$ cu semnificația din enunț.

Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Pe prima linie a fișierului de ieșire cibernetica.out se va afișa un singur număr natural, reprezentând numărul de ferestre determinat, în funcție de valoarea lui $C$, conform cerinței.

Restricții și precizări

• $C \in \{1, 2\}$;
• $1 \le N, K \le 10^6$;
• $1 \le a_i \le 10^6$, $1 \le i \le N$;
• Două ferestre de trafic $(i_1, j_1)$ și $(i_2, j_2)$ sunt diferite dacă $i_1 \ne i_2$ și/sau $j_1 \ne j_2$;
• O fereastră de trafic $(i, j)$ poate fi simultan suspectă și legitimă. Pentru un $C$ dat, se vor număra ferestrele din categoria solicitată, chiar dacă ele aparțin și celeilalte categorii.

Exemplul 1

cibernetica.in

1
5 2
1 1 2 3 2

cibernetica.out

6

Explicație

Elementele care apar de cel puțin $2$ ori sunt $1$ și $2$. Deci, ferestrele ce conțin cele două elemente egale cu $1$ sau cu $2$ sunt suspecte. Cele $6$ ferestre suspecte sunt:

• $(1, 2)$ cu adresele IP $[1, 1]$;
• $(1, 3)$ cu adresele IP $[1, 1, 2]$;
• $(1, 4)$ cu adresele IP $[1, 1, 2, 3]$;
• $(1, 5)$ cu adresele IP $[1, 1, 2, 3, 2]$;
• $(2, 5)$ cu adresele IP $[1, 2, 3, 2]$;
• $(3, 5)$ cu adresele IP $[2, 3, 2]$.

Exemplul 2

cibernetica.in

2
5 2
1 1 2 3 2

cibernetica.out

9

Explicație

Ferestrele legitime sunt: $(1, 3)$, $(1, 4)$, $(1, 5)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(3, 4)$, $(3, 5)$, $(4, 5)$.

Exemplul 3

cibernetica.in

1
4 3
2 2 1 2

cibernetica.out

1

Explicație

Singura fereastră suspectă este formată din întregul șir: $(1, 4) \rightarrow [2, 2, 1, 2]$.

Exemplul 4

cibernetica.in

2
4 3
2 2 1 2

cibernetica.out

0

Explicație

Nu există $3$ elemente cu valori distincte în șir, deci nu există ferestre legitime.

Exemplul 5

cibernetica.in

2
5 1
1 2 3 4 5

cibernetica.out

15

Explicație

Toate ferestrele care pot fi luate în considerare sunt legitime, pentru că oricare dintre ele conține cel puțin câte o adresă IP distinctă.