Preserving the Grid

Seunghyun has a $1 \times n$ grid board. Its cells are numbered 1 to $n$ from left to right. Exactly $k$ of the cells hold one horse each. A horse likes the board, so it visits every cell it can reach.

Seunghyun could not just watch the horses dirty his board, so he bought $d$ partitions. A partition goes on the line segment where two neighboring cells meet, at most one partition per segment, and a horse cannot cross a partition.

In the picture above, the horse on cell 5 visits cells 3, 4 and 5, and the horse on cell 8 visits cells 6, 7 and 8. The only preserved cells are cell 1 and cell 2.

Seunghyun wants to place the $d$ partitions so that the number of cells no horse visits is as large as possible. Help him by writing a program that finds the largest number of cells he can preserve.

The first line contains the board size $n$, the number of horses $k$, and the number of partitions $d$, separated by spaces.

The second line contains the integers $p_1, p_2, \ldots, p_k$, separated by spaces. $p_i$ is the number of the cell that holds horse $i$.

• $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 < \cdots < p_k \le n$

Print the largest number of cells that can be preserved when the $d$ partitions are placed well.