Programmer Linas decided to change his occupation and lifestyle. Without much thought, Linas moved to Paris and got employed to wash dishes in a small restaurant. He works hard in the small kitchen. To have more fun during breaks, Linas has brought a coffee pot.

During lunch time, dirty plates are passed to Linas through a small window. There are different sizes of plates, and Linas sorts the plates to different piles. When Linas gets a new plate, he washes it, quickly dries it and then, depending on the size of the plate, places it on the appropriate pile.

Since there’s not much room in the kitchen, Linas keeps his coffee pot on top of a pile of plates. If Linas wants to place a new plate on a pile with the coffee pot, he has to move the coffee pot to another pile.

Linas can’t stop thinking: “if I knew the order in which plates arrive, I could move the coffee pot less often.” Can you help Linas solve this task?

**Task**

Given the order of the plates that are passed to Lines, find the smallest possible number of coffee pot moves. At the beginning the pot can be placed on any pile.

**Input**

The first line contains two integers: the number of plates and the number of piles

.

Each of the next lines contains a single integer , the pile where -th plate has to be placed. These numbers are provided in the order of Linas getting the plates.

**Output**

Output a single integer – the smallest possible number of coffee pot moves Linas would have to make while washing the dishes.

**Sample Input**

8 3 3 1 2 1 1 3 3 2

**Sample Output**

2

The minimum number of coffee pot moves is 2. Before he starts his work, Linas can put the coffee pot on the first pile, and after washing the second plate – move the pot to the third pile. After washing the sixth plate, Linas should move the pot back to the first pile.

It is not possible to finish the job with fewer coffee pot moves, however the same result can be achieved differently.

Problem Source : Lithuanian Olympiad in Informatics

Solution

#include <iostream> #include <vector> #include <algorithm> #include <string.h> using namespace std; int main(){ int N, K; cin >> N >> K; // create vector vector<int> dish; int d; for (int i=0; i<N; i++){ cin >> d; dish.push_back(d); } // remove similar consecutives vector<int>::iterator it = unique(dish.begin(), dish.end()); dish.resize(distance(dish.begin(), it)); // start search bool pile[K+1]; memset(pile, 0, sizeof(pile)); int move = 0; int full = 0; for (it = dish.begin(); it != dish.end(); it++){ if (full == -1){ full = 0; move++; } if (pile[*it] == 0){ full++; pile[*it] = 0; } if (full == K-1){ full = -1; memset(pile, 0, sizeof(pile)); } } cout << move << endl; return 0; }