前処理として、机 \(s\) を左から \(k\) 番目に移動させることが可能であるような最小の \(k\) を各 \(s=1,2,\ldots,N\) について求めることを考えます。

この前処理によって、\(s_i>t_i\) を満たすクエリを各 \(O(1)\) で処理することが可能となります。

机 \(s\) を可能な限り左に持っていきたいので、

• \((\) 机 \(s\) を左に移動させる回数 \()-(\) 机 \(s\) を右に移動させる回数 \()\)

を最大化すればよいです。この式から、机 \(s\) を右に移動させることは無駄であることがわかります。また、机 \(s+1,\ldots,N\) について操作を行うことも無駄です。

\(A_i+A_s >K\) を満たす最大の \(i\,(<s)\) を \(m\) とします（存在しない場合は \(-1\) ）。

机 \(i\,(m+1\le i \le s-1)\) については、机 \(s\) よりも右側に移動させることが可能です。

机 \(i\,(1 \le i \le m)\) については、机 \(s\) よりも右側に移動させることができるための条件は以下です。

• \(A_i+\max(A_{i+1},\ldots,A_s) \le K\)

\(s=1,2,\ldots N\) の順番に見ていきます。\(i\) を固定したとき、\(A_i+ \max(A_{i+1},\ldots,A_s)\) は単調に増加していくので、\(i\) が上の条件を満たすかどうかが切り替わる回数は高々 \(1\) 回です。

よって、一点更新・区間和取得のデータ構造を用いて上の条件を満たす \(i\) の個数を求めることができます。

机 \(i\) をどれだけ右に持っていけるかも同様に求めることができます。したがって、この問題を \(O(N \log N)\) で解くことができました。

実装例：https://atcoder.jp/contests/nadafes2022_day1/submissions/30747421