Problem K
Mex Hex

A regular (non-magic) bobcat.
Photo by Becker1999

To defend itself against you, the magic bobcat (as the name suggests) tries to hurt you in unconventional ways. When it attacks, it casts a number of magic spells. Each spell is cast with a particular potential, which can be expressed as a natural number.¹ If you get hit with spells that have the potentials $p_1, p_2, \dots , p_n$, then the pain that you will feel from them is $\mathtt{mex}(\{ p_1, p_2, \dots , p_n\} )$, where $\mathtt{mex}$ denotes the Minimum Excluded Value.² Note that the spells do not hurt you immediately. Only after all spells are cast will you feel the pain based on the $\mathtt{mex}$ of their potentials.

To protect yourself, you bring a shield which can, also through magic, deflect the spells. Your shield has an activation duration $d$, which means that when you activate the shield, the next $d$ spells do not hit you. Afterwards, the shield must regenerate its magic and cannot be activated for the following $d$ spells. Apart from that, you can activate the shield as often as you want. To ensure that you give the magic bobcat a good scare, the mayor requested that you sneak up to it. As the bobcat would spot the glow of your activated magic shield, the earliest time you can activate the shield is when you stand before the culprit, right before it casts the first spell.

Figure 1: Illustration of Sample 3. The numbers in the boxes indicate the potentials of the spells. In this example, your shield’s activation duration is $d = 2$. By activating the shield right before the 5th, 9th, and 14th spell, you block the spells underlined in green. You cannot activate your shield for the spells that are underlined with a dashed red line, because it is regenerating its magic at these times.

You must now devise a tactic to sustain as little pain as possible. From studying the previous encounters with magic bobcats, you know the potentials of the spells that will be cast against you. What is the minimum pain you can receive from them if you activate your shield optimally?

Input

The input consists of:

• One line with two integers $n$ and $d$ ($1 \leq n \leq 10^5$, $1 \leq d \leq n$), the number of spells and the activation duration of your shield.

• One line with $n$ integers $p_1, \dots , p_n$ ($0 \leq p_i < n$), the potentials of the $n$ spells.

Output

Output a single integer, the minimum pain you can receive from the spells.

Notes

In the first sample, you can activate the shield for the first spell, let it regenerate its magic for the second, activate it again for the third, regenerate for the fourth, and activate again on the fifth spell. This means that only the two spells of potential $1$ hit you. As $\mathtt{mex}(\{ 1, 1\} ) = 0$, you receive $0$ pain.

In the second sample, no matter how you activate your shield, during the time it regenerates, a spell of potential $0$ and a spell of potential $1$ hit you. Thus, the $\mathtt{mex}$ of the spells that hit you is at least $2$. This amount of pain can be achieved by not using your shield at all.

In the third sample, you can use the shield as depicted in Figure 1. Then the spells that hit you have potentials $8$, $1$, $1$, $0$, $0$, $1$, $0$, $6$, and $4$. The $\mathtt{mex}$ of these potentials is $2$. It can be shown that there is no way of activating your shield so that the $\mathtt{mex}$ of the potentials of the remaining spells is $0$ or $1$.

For the fourth sample, recall that you cannot activate your shield any earlier than right before the first spell. Thus, you cannot block both spells of potential $0$. Instead, by blocking the second and third spell, all spells that hit you have potential $0$.

5 1
0 1 0 1 0

0

5 2
0 1 0 1 0

2

14 2
8 1 1 0 0 2 0 1 2 1 0 6 4 2

2

4 2
0 1 2 0

1