코드포시스

니콜라스는 코드포시스™ 선수권 대회에서 경쟁 낚시 선수 경력을 시작하고 싶어 한다. 경쟁할 수 있는 디비전은 매우 많지만, 니콜라스는 코드포시스™의 신규 참가자이므로 가장 낮은 디비전(디비전 1)에서 시작해야 한다. 니콜라스의 목표는 가능한 한 빨리 가장 높은 디비전(디비전 $K$)에 도달하여 그곳에서 낚시 대회에서 우승하는 것이다.

코드포시스™ 규칙에 따르면 대회 하나당 디비전을 하나만 올라갈 수 있으므로, 그는 각 디비전에서 적어도 한 번의 대회에 참가해야 한다. 니콜라스는 자신감이 매우 강하며, 다음 디비전으로 올라가기 위해 각 디비전에서 정확히 한 번의 대회만 필요할 것이라고 생각한다. 코드포시스™에서 대회가 열릴 때는 한 번에 하나의 디비전만 경쟁하며, 두 대회가 시간상 겹치는 일은 없다. 대회는 매년 동일한 일정도 따른다.

니콜라스는 연중 어느 날이든 코드포시스™에서 경쟁을 시작할 수 있다. 그가 가능한 한 빠르다고 말하는 것은, 자신이 참가하는지 여부와 관계없이 코드포시스™에서 열리는 대회 중 그가 처음 참가하는 대회와 가장 높은 디비전에서 처음으로 우승하는 대회 사이에 가능한 한 적은 수의 대회가 열려야 한다는 뜻이다. 니콜라스에게 필요한 대회 수를 계산하라.

채점

제출한 해답은 여러 테스트 케이스 그룹으로 이루어진 집합에 대해 채점된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$15$| $N \leq 10^2$

$2$ |$20$| $N \leq 10^3$

$3$ |$25$| $N = K$

$4$ |$40$| 추가 제한 없음

입력의 첫째 줄에는 두 정수 $N$와 $K$ ($1 \leq K \leq N \leq 10^6$)가 주어지며, 각각 연간 대회 수와 디비전 수를 나타낸다.

다음 줄에는 한 해의 대회 일정인 $N$개의 정수 $x_1, \dots, x_N$가 주어진다. ($1 \leq x_i \leq K$) $x_i$는 새해가 시작된 때부터 세었을 때 $i$번째 대회에서 경쟁하는 디비전이다. $1$부터 $K$까지의 각 디비전은 그해에 적어도 한 번의 대회가 있다.

니콜라스의 첫 대회와 디비전 $K$에서의 첫 우승 사이에 코드포시스™가 개최해야 하는 대회의 최소 개수를 나타내는 정수 하나를 출력한다.

니콜라스가 목표에 도달하는 가장 빠른 방법은 그해에 열리는 디비전 1의 두 번째 대회를 자신의 첫 대회로 삼는 것이다. 그런 다음 대회 네 번을 기다린 뒤 다음 해에 열리는 디비전 2의 첫 대회에 참가한다. 그런 다음 대회 세 번을 기다린 뒤 디비전 3에서 경쟁한다. 그런 다음 대회 다섯 번을 기다린 뒤 디비전 4에서 경쟁한다. 마지막으로 대회 두 번을 기다린 뒤 디비전 5에서 경쟁한다. 총 $1+(4+1)+(3+1)+(5+1)+(2+1) = 19$번의 대회가 필요하다.