Minimizing Song Information Reads

Igor has a playlist of n songs numbered from 1 to n. Today he will listen to m songs. When he plays the i^th song – whose position in the playlist is given by a_i – the system displays a contiguous block of k songs (i.e. an interval of length k) that must contain song a_i. When a song is displayed in any list it is read exactly once (even if it appears in several lists).

Your task is to choose, for each played song, an interval (of length k) from the playlist – subject to the constraint that the played song lies in it – so that the total number of distinct songs whose information is read is minimized.

Note that for song a_i the allowed intervals are exactly those whose starting position x satisfies

[ \max(1, a_i - k + 1) \le x \le a_i. ]

The union of all chosen intervals is the set of songs read. Compute its minimum possible size.

inputFormat

The input consists of two lines.

The first line contains three integers n m k (with 1 ≤ k ≤ n ≤ 10⁹ and 1 ≤ m ≤ 10⁵).

The second line contains m integers a₁, a₂, …, a_m (1 ≤ a_i ≤ n) which denote the positions of the songs as Igor listens to them. They are given in the order of play.

outputFormat

Output one integer – the minimum number of songs whose information must be read.

sample

5 3 2
1 2 3

3