机 \(s\) を左にのみ移動させることを考えたとき、移動できる回数の最大値を \(M_s\) とします。

\(A_i>\max(K,K-A_s)\) を満たす最大の \(i\ (<s)\) を \(m\) とします（存在しない場合は \(0\) ）。 また、 \(A_j+A_s \leq K\) を満たす \(j\ (m<j<s)\) の個数を \(t\) とします。

このとき、以下が成り立ちます（ただし、\(M_0=0\) とします）。

• \(M_s = M_m+t\)

証明は、\(j < m\) に対して、「机 \(j\) を机 \(i\) の右側に移動できること」と「机 \(j\) を机 \(m\) の右側に移動できること」が同値の条件であることから従います。

\(m\) は二分探索によって、\(t\) は平面走査によって、全ての \(s\) に対する値を \(O(N \log N)\) で求めることができます。あとは、\(s\) の昇順に \(M_s\) を求めていけばよいです。

右への移動も同様です。したがって、この問題を \(O(N \log N)\) で解くことができました。