\(i\) 番目の高橋くんの座標 \(X _ i\) に対して、\(X _ i=X ^ {\prime} _ i+i\) なる整数 \(X ^ {\prime} _ i\) を考えます。

このとき、操作は次のように言い換えられます。

\(T,G\) が与えられる。\(X ^ {\prime} _ T\leq G\) なら \(X ^ {\prime} _ i\in\lbrack X ^ {\prime} _ T,G\rbrack\) かつ \(T\leq i\) なるすべての \(i\) について、そうでないなら \(X ^ {\prime} _ i\in\lbrack G,X ^ {\prime} _ T\rbrack\) かつ \(i\leq T\) なるすべての \(i\) について、それぞれコストを \(|X ^ {\prime} _ i-G|\) 支払って \(X ^ {\prime} _ i\) を \(G\) に変更する。

制約より、\(X ^ {\prime} _ i\) は \(i\) についてつねに単調です。 そのため、上の操作で書き換えられる \(i\) も単一の区間を成します。 また、\(X ^ {\prime} _ i\) の値の条件から支払うコストは \(\displaystyle\sum _ {l\leq i\leq r}X ^ {\prime} _ i-G\times(r-l+1)\) もしくは \(\displaystyle G\times(r-l+1)-\sum _ {l\leq i\leq r}X ^ {\prime} _ i\) の形になります。

よって、この問題は以下のような方針で解くことができます。

• 区間代入および区間和・最小値・最大値を処理する遅延セグメント木などを用いて、上の操作を直接行う。
• \(X ^ {\prime} _ i\) の値が一致している区間をまとめて、std::map などの平衡二分木を用いて管理する。

実装例は以下のようになります。

この実装例では、遅延セグメント木を用いて実装を行っています。

#include <iostream>
#include <optional>
#include <limits>
#include <vector>
#include <atcoder/lazysegtree>

int main() {
    using namespace std;
    constexpr unsigned offset{100000000};
    unsigned N;
    cin >> N;

    // セグメント木をつくる
    auto segment_tree = [] (const auto N) {
        // (区間の長さ, 区間内の総和, 区間内の最小値, 区間内の最大値) を管理する
        struct segment_tree_value {
            unsigned length;
            unsigned long sum;
            unsigned min, max;
        };
        // 区間への代入
        using assign_type = optional<unsigned>;
        atcoder::lazy_segtree<segment_tree_value, [](const auto& lhs, const auto& rhs) -> segment_tree_value {
            // 区間をいい感じに合併する
            const auto& [l_len, l_sum, l_min, l_max]{lhs};
            const auto& [r_len, r_sum, r_min, r_max]{rhs};
            return {l_len + r_len, l_sum + r_sum, min(l_min, r_min), max(l_max, r_max)};
        }, []() -> segment_tree_value {
            // 単位元は長さ 0 の区間
            return {0U, 0UL, offset * 2, 0U};
        }, assign_type, [](const auto& f, const auto x) {
            // 代入クエリがあるなら、それで埋める
            return f ? segment_tree_value{x.length, static_cast<unsigned long>(*f) * x.length, *f, *f} : x;
        }, [](const auto& f, const auto &x){
            return f ? f : x;
        }, []{return std::nullopt;}> result(N);

        for (unsigned i{}; i < N; ++i) {
            unsigned X;
            cin >> X;
            X += offset;
            X -= i;
            result.set(i, {1, X, X, X});
        }
        return result;
    }(N);

    unsigned Q;
    cin >> Q;
    unsigned long ans{};
    for (unsigned i{}; i < Q; ++i) {
        unsigned T, G;
        cin >> T >> G;
        --T;
        G += offset;
        G -= T;

        // 現在地は長さ 1 の区間を取ってきたときの 合計 = 最小値 = 最大値
        const auto now_position{segment_tree.get(T).max};
        if (now_position < G) { // いま、目的地より西側にいるなら
            // 現在地より東、目的地より西にいる高橋くんを列挙し、
            const auto upper_bound{segment_tree.max_right(T, [G](const auto& v){return v.max < G;})};
            const auto& [length, sum, min, max]{segment_tree.prod(T, upper_bound)};
            // かかる移動回数を求める
            ans += static_cast<unsigned long>(length) * G - sum;
            // 間にいる高橋くん全員を移動させる
            segment_tree.apply(T, upper_bound, G);
        } else { // 東側にいるなら、
            // 現在地より西、目的地より東にいる高橋くんを列挙し、
            const auto it{segment_tree.min_left(T + 1, [G](const auto& v){return v.min > G;})};
            const auto& [length, sum, min, max]{segment_tree.prod(it, T + 1)};
            // かかる移動回数を求める
            ans += sum - static_cast<unsigned long>(length) * G;
            // 間にいる高橋くん全員を移動させる
            segment_tree.apply(it, T + 1, G);
        }
    }

    cout << ans << endl;
    return 0;
}