의자 게임

HI-ARC의 첫 MT가 시작되었다. 운영진들은 재밌는 의자 게임을 준비하였다.

방 안에는 $1$번, $2$번, $\dots$, $N$번 의자가 순서대로 놓여 있다. 즉, 가장 오른쪽의 $N$번 의자를 제외하면, $i$번 의자의 오른쪽에는 $i+1$번 의자가 있다. 각 의자에는 $N$명의 참가자가 앉아 있으며, 모든 참가자는 $1$ 이상 $N$ 이하의 정수인 등번호를 부여받았다. 등번호는 같을 수도 있다.

게임은 우승자가 나오기 전까지 다음 규칙에 따라 진행된다.

1. 각 참가자는 자신의 오른쪽 의자로 이동한다. 단, 가장 오른쪽 의자에 앉은 참가자는 $1$번 의자로 이동한다.
2. 연속으로 앉아 있는 $K$명의 참가자가 자리를 재배열해 자신들의 등번호와 의자 번호를 똑같이 만들 수 있으면, 그 참가자들이 게임에서 공동 우승한다. 우승자가 없다면 규칙 1로 돌아간다.

하지만 이럴 수가! 게임이 진행되던 도중, 운영진들은 이 게임이 영원히 끝나지 않을 수도 있다는 것을 깨달았다. 이를 해결하기 위해 운영진들은 규칙 2 이후 규칙 1로 돌아가기 전에, 원한다면 아래 방식으로 참가자를 한 명 추가할 수 있다.

• 현재 $X$개의 의자가 있다면, $X$번 의자의 오른쪽에 $X+1$번 의자를 추가하고 새로운 참가자가 거기에 앉는다. 이 참가자의 등번호는 운영진이 원하는 양의 정수로 정할 수 있다.

운영진들은 게임의 흥을 깨지 않도록 최소한의 참가자만 추가하고 싶어 한다. 게임이 유한한 시간 안에 끝나게 하려면, 운영진들은 최소 몇 명의 참가자를 추가해야 할까?

다음과 같이 입력이 주어진다.

$N\ K$

$a\_1\ a\_2\\,\dots\ a\_N$

게임이 유한한 시간 내에 끝나기 위해 추가해야 하는 최소 인원수를 출력한다.

• $N$은 의자와 참가자의 수, $K$는 우승자의 최소 인원수이다. ($1 \le K \le N \le 100\\,000$)
• $a\_i$는 초기에 $i$번 의자에 앉은 참가자의 등번호다. ($1 \le a\_i \le N$)
• 입력으로 주어지는 모든 수는 정수다.