答えは、\(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)\) です。