答えは、$A$ の連続する $M$ 要素であって $i$ を $1$ つも含まないようなものが存在するような最小の非負整数 $i$ です。

$\mathrm{pos}_i$ : $A_j = i$ となるような $j$ を昇順に入れた配列
を計算しておけば、$i$ の昇順に、 $\mathrm{pos}_{i, j} - \mathrm{pos}_{i, j - 1} > M$ となるような $j$ が存在するかを判定すればよいです。ただし端は注意が必要です。別途処理するか、最初に $\mathrm{pos}$ に $0$ と $N + 1$ も入れるとよいです。
計算量は $O(N)$ です。