시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB167797458.268%

문제

도윤이에게는 $N$행 $N$열의 격자로 이루어진 모눈종이가 하나 있습니다. 도윤이가 모눈종이를 자습실에 두고 놀다 왔더니 다른 친구가 각 행마다 정확히 한 칸을 골라 총 $N$개의 낙서를 하고 갔습니다. 모눈종이를 버릴 수 없는 도윤이는 여기에 아래 조건을 만족하도록 색종이를 덧붙여 낙서를 완전히 가리려고 합니다.

  • 색종이는 가로와 세로 길이가 정수인 직사각형 모양이며, 모눈종이의 격자와 평행한 방향으로 각 격자칸을 완전히 덮도록 붙여야 합니다. 다시 말해 색종이가 한 격자칸의 일부만 덮도록 놓는 것은 불가능합니다.
  • 어떤 두 색종이도 공통으로 덮는 행이 존재하지 않아야 합니다. 즉, 모든 행에는 최대 하나의 색종이만 붙일 수 있습니다.
  • 각 색종이의 넓이는 $K$ 이하여야 합니다.

아래 그림의 왼쪽은 $K = 6$일 때 위 조건을 만족하도록 색종이를 붙인 모습이며, 오른쪽은 두 색종이 모두 $3$행을 공통으로 덮으므로 위 조건을 만족하지 않습니다.

$N$, $K$가 주어지고 각 행에 친구가 낙서한 위치가 주어질 때 도윤이에게 필요한 색종이 수의 최솟값을 구해봅시다.

입력

첫째 줄에 양의 정수 $N$, $K$가 공백으로 구분되어 주어집니다.

둘째 줄부터 각 행에서 친구가 낙서한 위치를 나타내는 정수 $a_{1},a_{2},\dots , a_{N}$이 공백으로 구분되어 주어집니다. 이는 $i$행 $a_{i}$열 위치에 친구가 낙서를 남겼다는 뜻입니다.

출력

첫째 줄에 필요한 색종이 수의 최솟값을 출력합니다.

제한

  • $1\le N\le 10^{6}$
  • $1\le K\le N^{2}$
  • $1\le a_{i}\le N$ $(1\le i\le N)$

서브태스크

번호배점제한
15

$K = 1$

213

$a_1=a_2=\cdots =a_{N}$

328

$a_1 \le a_2 \le \cdots \le a_{N}$

454

추가 제한 조건이 없습니다.

예제 입력 1

5 6
2 1 1 5 4

예제 출력 1

2

예제 입력 2

5 2
2 1 1 5 4

예제 출력 2

4

예제 입력 3

5 4
2 1 1 5 4

예제 출력 3

3

채점 및 기타 정보

  • 예제는 채점하지 않는다.