의자 게임

드디어 HI-ARC의 첫 MT가 시작되었다. HI-ARC의 운영진들은 재밌는 의자 게임을 준비하였다. 방 안에는 $1$번, $2$번, $\dots$, $N$번 의자가 순서대로 놓여있다. 즉, 가장 오른쪽에 있는 $N$번 의자를 제외하면, $i$번 의자의 오른쪽에는 $i+1$번 의자가 있다. 각 의자에는 $N$명의 참가자가 앉아있으며, 모든 참가자는 $1$ 이상 $N$ 이하의 정수인 등번호를 부여받았다. 등번호는 같을 수도 있다.

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

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

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

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

운영진들은 게임의 흥을 깨지 않기 위해 최소한의 참가자만을 추가하고 싶다. 게임이 언젠가는 끝나게 하기 위해서, 운영진들은 최소 몇 명의 참가자를 추가해야 할까?

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

$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$)
• 입력으로 주어지는 모든 수는 정수다.