Description

On a hot summer day, having a freshly squeezed, ice-cold juice is a delightful treat. Seeing this business opportunity, Xiao Wang opened a juice shop near the school. However, he recently ran into a not-so-small, not-so-big problem: Xiao Wang prepared $K$ juicers in his shop, and each juicer can only squeeze one kind of juice. Over a period of time, when a customer orders a certain type of juice, if there happens to be a juicer that has already been used for that juice, then he can directly use that juicer again for the customer. But if the ordered juice is a new type, he needs to find a clean juicer to use. Here comes the issue: if there are still unused clean juicers, that’s fine; otherwise, Xiao Wang needs to take one that was used earlier and wash it. Washing takes a lot of time and water. Being economically minded, Xiao Wang wants to know, given the known sequence of customer orders, what is the minimal number of times the juicers must be washed? Assume that all juicers are clean at the start. For convenience, we number the juices as $1$ (orange), $2$ (apple), $3$ (grape), and so on.

[Friendly reminder: This shop does not sell mixed juice.]

Input Format

For each test case, the first line contains two integers $K, N$, where $K$ is the number of clean juicers Xiao Wang has prepared, and $N$ is the number of customers waiting in line. The next $N$ lines each contain one integer, representing the type of juice ordered by a customer, denoted as $X_i$.

Output Format

Output the minimal number of times the juicers must be washed for the given request sequence.

2 7
1
2
3
1
3
1
3

1

Hint

$1 \le K \le 10$, $1 \le N \le 100$.

$1 \le X_i \le 100$.

Translated by ChatGPT 5