Filing Farmer John’s Emails

Farmer John is behind in filing his emails. His computer screen shows a vertical list of folders on the left and a vertical list of emails on the right. There are \(M\) folders numbered \(1,2,\dots,M\) (\(1\le M\le 10^4\)) and \(N\) emails numbered \(1,2,\dots,N\) (\(1\le N\le 10^5\)). The \(i\)th email must be filed in folder \(f_i\) (\(1\le f_i\le M\)).

However, due to his small screen, Farmer John can only view \(K\) (\(1\le K\le \min(N, M)\)) folders at a time and \(K\) emails at a time. Initially, the folder view shows folders \(1 \ldots K\) and the email view shows emails \(1 \ldots K\). To see later folders or emails, he must scroll downward. When he scrolls one step in the folder list, the visible folders become \(2,3,\dots,K+1\), and similarly for emails.

When FJ drags an email into its correct folder (which must be visible on the left), that email is removed from the email list and the emails below shift upward. For example, if the visible emails are \(1,2,3,4,5\) and email 3 is filed, the new visible emails become \(1,2,4,5,6\).

One quirk is that FJ's mouse cannot scroll upward. The only way to get a semblance of upward scrolling is when he is viewing the last set of \(K\) emails (or all remaining emails if fewer than \(K\)) and he files one; in this case the view is refreshed to show the last \(K\) unfiled emails.

Your task is to decide whether it is possible to file all of the emails using some valid sequence of moves. At any time, FJ may:

• Drag any email currently visible into its designated folder provided that folder is visible. (A folder \(x\) is visible if \(x\) lies in the current folder view, which spans from \(F\) to \(F+K-1\) for some \(F\) with \(1\le F\le M\). The folder view can be scrolled downwards as needed, but never upward.)
• Scroll the folder view downward (by one step) if the current view does not allow any filing.

Determine if there exists an order of filing the emails such that every email is eventually filed.

inputFormat

The first line contains three integers \(M, N, K\). The second line contains \(N\) integers \(f_1, f_2, \ldots, f_N\), where \(f_i\) is the folder required for the \(i\)th email.

outputFormat

Output a single line containing either YES if it is possible to file all emails, or NO otherwise.

sample

5 5 2
1 2 1 2 1

YES