Rock Jumping Challenge

Xiao D is standing on the bank at coordinate \(0\) and wishes to first reach the opposite bank at coordinate \(N\) and then return to \(0\). Before reaching \(N\), he can only jump to strictly larger coordinates; after reaching \(N\), he can only jump to strictly smaller coordinates. There are \(M\) rocks located in the middle of the river (i.e. between \(0\) and \(N\)), and Xiao D wants to land on each rock exactly once. In addition, every jump he makes must have a length of at least \(S\) (there is no upper limit on the jump length).

The task is to determine whether Xiao D can complete his goal by choosing an appropriate order in which to visit the rocks. Note that during his journey, the rocks that are visited on the way forward (from \(0\) to \(N\)) must appear in strictly increasing order, and the remaining rocks (visited on the return journey from \(N\) to \(0\)) must appear in strictly decreasing order.

Input format: The first line contains three integers \(N\), \(M\) and \(S\). The second line contains \(M\) integers representing the coordinates of the rocks. It is guaranteed that \(0 < r_i < N\) for each rock. The rock coordinates may not be given in sorted order.

Output format: Output YES if Xiao D can complete his goal under the given conditions. Otherwise, output NO.

Note: You may partition the rocks (after sorting them in increasing order) into two contiguous segments: one for the forward journey and one for the backward journey. For the forward journey, if the forward segment is non-empty, the conditions are:

[ \begin{aligned} & a_1 - 0 \ge S,\ & a_{i} - a_{i-1} \ge S \quad \text{for } 2 \le i \le k,\ & N - a_k \ge S. \end{aligned} ]

For the backward journey (if the segment is non-empty), if the backward segment is \(a_{k+1}, a_{k+2}, \ldots, a_M\) (in sorted order) then in the descending order the conditions are:

[ \begin{aligned} & N - a_M \ge S,\ & a_{i+1} - a_i \ge S \quad \text{for } i = k+1, \ldots, M-1,\ & a_{k+1} - 0 \ge S. \end{aligned} ]

If either segment is empty, the corresponding jump (\(0 \to N\) or \(N \to 0\)) must be at least \(S\). If there exists any valid partition index \(k\) with \(0 \le k \le M\) satisfying the above conditions, then the answer is YES; otherwise, the answer is NO.

inputFormat

The input consists of two lines. The first line contains three integers \(N\), \(M\), and \(S\) separated by spaces, where \(N\) is the coordinate of the opposite bank, \(M\) is the number of rocks, and \(S\) is the minimum jump length. The second line contains \(M\) integers representing the coordinates of the rocks, separated by spaces.

outputFormat

Output a single line containing either YES if Xiao D can complete his journey under the stated conditions, or NO otherwise.

sample

10 3 3
3 6 7

YES