Kako se mali Draganče iz trećeg zadatka nije proslavio u matematici i programiranju, roditelji su mu smanjili džeparac. Zato je on rešio da iskoristi svoju veliku kolekciju DVD filmova i odlučio da prodaje filmove po niskim cenama. Svaki film se nalazi na jednom DVD-u, a na Dragančetovom hard disku može stati najviše k filmova. Procedura rezanja je sledeća: ukoliko se traženi film nalazi na hard disku, Draganče odmah počinje sa rezanjem; u suprotnom on mora da nađe odgovarajući DVD i presnimi ga na hard disk. Ako na disku nema slobodnog prostora, on mora da obriše neki film. Traženje DVD-a i presnimavanje iziskuje puno vremena, i zato Draganče želi da smanji taj broj. Na početku je njegov disk prazan.

On je napravio spisak poručenih filmova i zna tačno redosled n kupaca koji dolaze da nasnime omiljeni film. Draganče je uspeo da minimizira broj prebacivanja filmova na HDD (a samim tim i čekanje kupaca). Da li i vi možete da izračunate koliko će najmanje puta Draganče ipak morati da presnimi neki film na hard disk?

Ulaz:

(Ulazni podaci se nalaze u datoteci filmovi.in) U prvom redu datoteke se nalaze dva prirodna broja n i k. Broj n predstavlja broj naručenih filmova, a broj k je broj filmova koji može da stane na disku. U sledećih n redova nalaze se redni brojevi filmova a[i] koje kupci uzimaju, poređani po vremenu dolaska

Izlaz:

(Izlazne podatke upisati u datoteku filmovi.out) U prvom i jedinom redu štampati minimalan broj presnimavanja DVD-a na hard disk.

Ograničenja:

• 1 ≤ n ≤ 10000
• 1 ≤ k ≤ 500
• 1 ≤ a[i] ≤ 10000
• vremensko ograničenje za izvršavanje programa je 1 s.

Primer 1:

2 5
1
2
2
4
1

3

Objašnjenje:

lj Kako je hard disk na početku prazan, Draganče mora da presnimi film sa rednim brojem 1. Zatim, mora da presnimi film broj 2. Sledeći kupac naručuje film koji se već nalazi na disku, tako da ga Draganče odmah nareže. Naredni kupac traži film 4, tako da Draganče briše film broj 2 i presnimava preko film broj 4. Poslednji film koji se traži je broj 1, tako da Draganče ne mora da ga traži, jer se na hard disku nalaze filmovi 4 i 1.

Primer 2:

3 10
2
3
2
1
5
2
4
5
3
2

6

/*
  Niz a [] -  redni brojevi filmova
  Niz p [] -  niz indeksa, tako da je niz a [p [i]] sortiran
  Niz q [] -  indeksi filmova koji su trenutno na disku
  Niz next [] -  sledeci index sa jednakim rednim brojem, ili n ako takav ne postoji
  n -      broj filmova
  k -      kapacitet diska
*/
/*
#include <iostream>
#include <fstream>
#define MaxN 10001
#define MaxK 501

using namespace std;
int a [MaxN], p [MaxN], next [MaxN], q [MaxK];
int n, k, sol;

void input ()
{
  ifstream in ("filmovi.in");
  in >> n >> k;
  for (int i = 0; i < n; i++)
    in >> a [i];
  in.close ();
}

void output ()
{
  ofstream out ("filmovi.out");
  out << sol << endl;
  out.close();
}

void quicksort (int l, int r)
{
  int i, j, pivota, pivoti, tmp;

  i = l;
  j = r;
  tmp = (l + r) / 2;
  pivota = a [p [tmp]];
  pivoti = p [tmp];
  do
  {
    while ((i <= r) && ((a [p [i]] < pivota) || ((a [p [i]] == pivota) && (p [i] < pivoti))))
      i++;
    while ((j >= l) && ((a [p [j]] > pivota) || ((a [p [j]] == pivota) && (p [j] > pivoti))))
      j--;
    if (i <= j)
    {
      tmp = p [i];
      p [i] = p [j];
      p [j] = tmp;
      i++;
      j--;
    }
  }
  while (i < j);
  if (i < r)
    quicksort (i, r);
  if (l < j)
    quicksort (l, j);
}

void solve ()
{
  int i, m, j, ind, max, found;

  sol = 0;
  for (i = 0; i < n; i++)
    p [i] = i;
  quicksort (0, n - 1);
  for (i = 0; i < n; i++)
    if ((i + 1 < n) && (a [p [i]] == a [p [i + 1]]))
      next [p [i]] = p [i + 1];
    else
      next [p [i]] = n;
  m = 0;
  for (i = 0; i < n; i++)
  {
    found = 0;
    ind = 0;
    max = -1;
    for (j = 0; j < m; j++)
      if (a [q [j]] == a [i])
      {
        q [j] = i;
        found = 1;
        break;
      }
      else
      {
        if (max < next [q [j]])
        {
          max = next [q [j]];
          ind = j;
        }
      }
    if (found == 0)
    {
      if (m < k)
      {
        q [m] = i;
        m++;
      }
      else
        q [ind] = i;
      sol++;
    }
  }
}

int main ()
{
  input ();
  solve ();
  output ();
  return 0;
}
*/