Se considera un calculator ce are o memorie RAM cu o capacitate de K pagini de memorie si un proces ce se afla in executie pe acest calculator. Se stie ca orice proces are un spatiu de adrese in memoria virtuala, care are, de obicei, o dimensiune mai mare decat memoria RAM. Se cunosc cele N pagini de memorie virtuala accesate de proces, in ordinea in care ele sunt accesate. De fiecare data cand procesul acceseaza o pagina avand un numar X, sistemul de operare verifica daca pagina respectiva se afla in memoria RAM. Daca sistemul de operare gaseste pagina in memoria RAM, pagina poate fi accesata imediat de catre proces. Daca pagina X nu se afla in RAM, atunci ea trebuie adusa de pe disc intr-una dintre cele K locatii din memoria RAM, aceasta operatie fiind foarte costisitoare din punct de vedere al timpului de executie. In cazul in care exista deja K pagini de memorie virtuala in memoria RAM, una dintre aceste pagini trebuie scrisa pe disc si eliminata din memorie, pentru a aduce in locul ei pagina X accesata.
Cunoscand dimensiunea memoriei RAM, numarul de pagini de memorie accesate de procesul aflat in executie, precum si numerele paginilor respective (in ordinea in care acestea sunt accesate), determinati numarul minim de operatii de aducere a unei pagini de pe disc in memoria RAM. In mod evident, acest numar depinde foarte mult de paginile alese pentru a fi eliminate din memoria RAM, atunci cand apare aceasta situatie. Initial, se considera ca memoria RAM nu contine nici o pagina de memorie virtuala.

Date de intare

Pe prima linie a fisierului vmem.in se afla numerele intregi N si K, separate printr-un spatiu. Pe urmatoarea linie se afla N numere intregi, reprezentand numerele paginilor de memorie accesate de catre proces. Paginile sunt date in ordinea in care sunt accesate.

Date de iesire

In fisierul de iesire vmem.out veti afisa o singura linie pe care va fi scris numarul minim necesar de operatii de aducere a unei pagini de memorie de pe disc in memoria RAM.

Restrictii si precizari

1 <= N <= 100 000
1 <= K <= N
Numerele paginilor sunt numere intregi din intervalul [1,100 000 000].

Exemplu

Timp maxim de executie/test: 0.25 secunde

As.drd.ing. Mugurel Ionut Andreica
Universitatea Politehnica Bucuresti, Facultatea de Automatica si Calculatoare
mugurel_ionut@yahoo.com