Горные лыжи

시간 제한2초메모리 제한512 MB

요약

타냐가 반드시 스키장에 있었던 날들과 한 번의 여행 길이 k가 주어질 때, 그녀가 도시에서 보낼 수 있었던 겨울 날의 최대 일수를 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 구간, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

Суровая зима в Санкт-Барнаурге длится $n$ дней. Таня очень любит кататься на лыжах и часто выезжает на близлежащий горнолыжный курорт в Тбиатыкенте. Так, про некоторые дни последней зимы Таня помнит, что была в этот день на горнолыжном курорте --- ведь она выкладывала своё фото со склона в тот день в социальной сети SkiForces. Про другие дни никакой информации нет.

Известно, что Таня всегда ездит на курорт одинаково: она выезжает утром некоторого дня, проводит на курорте ровно $k$ дней и возвращается вечером $k$ -го дня поездки. При этом могло оказаться, что Таня снова поехала на курорт на следующий день после окончания предыдущей поездки. Те, дни, когда Таня не ездила на горнолыжный курорт, она провела в городе.

Зима закончилась, и подруги говорят Тане, что она слишком много катается на лыжах. Чтобы понять, так ли это, Таня хочет выяснить, каким могло быть максимальное количество зимних дней, которые провела в городе.

Таня могла первый раз поехать на курорт до начала зимы и могла закончить последнюю поездку после окончания зимы.

입력

В первой строке находятся три целых положительных числа $n$ , $k$ и $m$ --- продолжительность зимы в днях, длительность одной поездки на горнолыжный курорт в днях и количество дней, в которые Таня точно была на курорте ( $1 \le k \le n \le 10^9$ , $1 \le m \le 2 \cdot 10^5$ , $m \le n$ ).

Во второй строке находятся $m$ чисел $d\_1, d\_2, \ldots, d\_m$ --- номера дней в которые Таня точно была на курорте ( $1\le d\_i \le n$ ). Каждый день перечислен не более одного раза.

출력

Выведите единственное целое число --- максимальное количество зимних дней, в которые Таня не была на горнолыжном курорте.

힌트

В первом примере Таня могла быть на курорте два раза: первый раз начиная за день до зимы и заканчивая в 1-й день зимы; второй раз начиная в последний день зимы и заканчивая в 1-й день после зимы.

Таким образом, Таня могла провести в городе второй и третий дни зимы.

Во втором примере Таня могла быть на курорте один раз, например, начиная со второго дня зимы и заканчивая пятым днём зимы. Таким образом, Таня могла провести в городе три дня --- в первый, в шестой и в седьмой дни зимы.

예제4

예제 1
입력
```
4 2 2
1 4
```
예상 출력
```
2
```
예제 2
입력
```
7 4 3
4 3 5
```
예상 출력
```
3
```
예제 3
입력
```
5 1 5
5 4 3 2 1
```
예상 출력
```
0
```
예제 4
입력
```
13 3 6
3 5 6 8 9 11
```
예상 출력
```
4
```