Î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 ai (1 ≤ i ≤ 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 ≤ i ≤ j ≤ N și este reprezentată de secvența de IP-uri [ai, ai+1, …, aj].
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ța

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 ai

Numerele aflate pe aceeași linie a fișerului 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 ∈ {1, 2}
• 1 ≤ N, K ≤ 1.000.000
• 1 ≤ ai ≤ 1.000.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
• Două ferestre de trafic (𝑖1, 𝑗1) și (𝑖2, 𝑗2) sunt diferite dacă i1 ≠ i2 și/sau j1 ≠ j2.
• 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.
• Pentru 18 puncte, K = 1
• Pentru 17 puncte, C = 1 și 1 ≤ N, K ≤ 100
• Pentru 12 puncte, C = 1 și 1 ≤ N, K ≤ 1000
• Pentru 7 puncte, C = 1 și 1 ≤ ai ≤ 2, pentru orice i=1..n
• Pentru 9 puncte, C = 1, fără alte restricții
• Pentru 14 puncte, C = 2 și 1 ≤ N, K ≤ 100
• Pentru 10 puncte, C = 2 și 1 ≤ N, K ≤ 1000
• Pentru 8 puncte, C = 2 și 1 ≤ ai ≤ 2, pentru orice i=1..n
• Pentru 5 puncte, C = 2, fără alte restricții

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) −→ [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ă.