시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (추가 시간 없음) 1024 MB 116 30 23 29.487%

문제

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

출력

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

예제 입력 1

3 3
3 1 2

예제 출력 1

0

$\require{extpfeil}\Newextarrow{\xRightarrow}{5,5}{0x21D2}$$[3, 1, 2]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[2, 3, 1]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[1, 2, 3]$

규칙 2로 인해, $[\underline{1, 2, 3}]$ 이 승리한다.

예제 입력 2

4 3
1 4 4 4

예제 출력 2

2

$\require{extpfeil}\Newextarrow{\xRightarrow}{5,5}{0x21D2}$$[1, 4, 4, 4]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[4, 1, 4, 4]$ $\xRightarrow[\textsf{$2$ 추가}]{}$ $[4, 1, 4, 4, 2]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[2, 4, 1, 4, 4]$ $\xRightarrow[\textsf{$3$ 추가}]{}$ $[2, 4, 1, 4, 4, 3]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[3, 2, 4, 1, 4, 4]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[4, 3, 2, 4, 1, 4]$

규칙 2로 인해, $[4, \underline{3, 2, 4}, 1, 4]$ 이 승리한다.