격자 보존하기 Batch Compilation commands

승현이는 $1 \times n$ 크기의 격자판을 가지고 있습니다. 각 칸에는 $1$ 이상 $n$ 이하의 자연수 번호가 왼쪽에서부터 차례대로 붙어있습니다. 이 중 $k$개의 칸에는 말이 하나씩 놓여 있는데, 이 말들은 격자들을 좋아해서, 도달 가능한 모든 격자판을 방문합니다. 말들이 자신의 격자판을 더럽히는 것을 보고만 있을 수 없었던 승현이는 $d$개의 칸막이를 구매했습니다. 각 칸막이는 인접한 두 격자가 만나는 선분 위에 놓을 수 있으며, 말들은 칸막이를 지나갈 수 없습니다.

위 그림에서, 지금 5번 격자에 있는 말은 3번, 4번, 5번 격자를 모두 방문하고, 8번 격자에 있는 말은 6번, 7번, 8번 격자를 모두 방문합니다. 보존되는 격자는 1번 격자와 2번 격자뿐입니다.

승현이는 $d$개의 칸막이들을 적절히 배치하여 어떤 말도 방문하지 않은 격자의 수를 최대화하려고 합니다. 하지만 그 방법은 잘 모르겠다고 합니다. 승현이를 도와 보존할 수 있는 최대 격자의 수를 구하는 프로그램을 작성하세요.

입력 형식

첫 번째 줄에 격자판의 크기 $n$, 말의 수 $k$, 칸막이의 수 $d$가 공백을 사이로 두고 주어집니다.

두 번째 줄에는 $k$개의 정수 $p_{1}, p_{2}, ..., p_{k}$가 공백을 사이로 두고 주어집니다. 이 중 $i$ ($1 \le i \le k$)번째 정수 $p_{i}$는 $i$번 말이 위치한 칸의 번호를 나타냅니다.

출력 형식

승현이가 $d$개의 칸막이들을 잘 설치하여 보존할 수 있는 격자의 수의 최댓값을 출력합니다.

제약 조건

• $2 \le n \le 10^{9}$
• $1 \le k \le min(10^{5}, n)$
• $1 \le d \le n - 1$
• $1 \le p_{1} < p_{2} < ... < p_{k - 1} < p_{k} \le n$

부분문제

부분문제	점수	n	k	d
1	9	≤ 20	≤ n	≤ n - 1
2	17	≤ 105	= 3	= 3
3	22	≤ 106	≤ 103	≤ 102
4	17	≤ 109	≤ 105	≤ 103
5	35	≤ 109	≤ 105	≤ n - 1

예제

입력

15 4 3
3 5 10 11

출력

8