We can prove that \(a_{i} = a_{N+1}\) for all \(i \ge N+1\) by using mathematical induction.

Base case. \(i=N+1\): Obvious.

Induction step. Assume that it is true when \(i=N+1, \cdots , r\). (\(r \ge N+1\))

By the definition of \(a_{N+1}\), the number of elements less than \(a_{N+1}\) among \(a_1 , \cdots , a_N\) is less than or equal to \(K-1\), and the number of elements greater than \(a_{N+1}\) among \(a_1 , \cdots , a_N\) is less than or equal to \(N-K\).

By the assumption, the number of elements less than \(a_{N+1}\) among \(a_{r-N+1}, \cdots , a_{r}\) is less than or equal to \(K-1\). Thus \(a_{r+1} \ge a_{N+1}\).

On the other hand, the number of elements greater than \(a_{N+1}\) among \(a_{r-N+1}, \cdots , a_{r}\) is less than or equal to \(N-K\). Thus \(a_{r+1} \le a_{N+1}\). Therefore, we have \(a_{r+1} = a_{N+1}\), so it is also true when \(i=r+1\).

Hence the answer is very simple. When \(M \le N\), the answer is \(a_M\). When \(M > N\), the answer is \(a_{N+1}\), which is the \(k\)-th element among \(a_1 , \cdots , a_N\) when sorting in nondecreasing order.

The total time complexity is \(\mathcal{O} \left( N \log N \right)\).