Farmer John's Crosswalk Repairs

Farmer John's long road has N crosswalks numbered from 1 to \(N\). At each crosswalk, there is an electric crossing signal that lights up with a green cow icon when it is safe for the cow to cross and red otherwise. Unfortunately, a recent electrical storm damaged some of these signals.

You are given the number of crosswalks \(N\), the required length \(K\) for a contiguous block of working signals, and a list of \(D\) damaged signal indices. Your task is to determine the minimum number of signals Farmer John needs to repair so that there is at least one contiguous block of \(K\) working signals.

The mathematical formulation of the problem is: Let \(A\) be an array of length \(N\) where \(A_i = 1\) if the signal at crosswalk \(i\) is damaged and 0 otherwise. Find the minimum sum over any contiguous subarray of length \(K\). That is, find \(\min_{1 \leq i \leq N-K+1} \sum_{j=i}^{i+K-1} A_j\).

inputFormat

The first line contains three integers \(N\), \(K\) and \(D\) (the number of damaged signals).
The second line contains \(D\) distinct integers, each representing the index of a damaged signal.

\(1 \leq N \leq 100000\), \(1 \leq K \leq N\), and the indices are between 1 and \(N\).

outputFormat

Output a single integer: the minimum number of repairs required so that there exists a contiguous block of \(K\) working signals.

sample

10 6 3
2 10 1

0