大和証券プログラミングコンテスト2022 Spring (AtCoder Regular Contest 138) A - Larger Score (400)
値を1大きくすればいいので大小関係だけ持っておけばいいので配列の値を座標圧縮しておく
k番目以降の値の位置をセグ木に入れておく
前k個についてそれぞれ以下を行う
セグ木から自分の値より大きい値の位置の最小値を取得する
その地点までの距離で答えを小さくできるなら更新する
今の位置の値を大きくするにはその位置までの全てでスワップが必要なため
各操作でセグ木を使っているので$ \mathcal{O}(N \log N)