For the coordinate \(X _ i\) of the \(i\)-th person, consider an integer \(X ^ {\prime} _ i\) defined as \(X _ i=X ^ {\prime} _ i+i\).

Then, the operation can be rephrased as follows:

You are given \(T\) and \(G\). Pay a cost of \(|X ^ {\prime} _ i-G|\) to set \(X ^ {\prime} _ i\) to \(G\) for all \(i\) such that, if \(X ^ {\prime} _ T\leq G\), such that \(X ^ {\prime} _ i\in\lbrack X ^ {\prime} _ T,G\rbrack\) and \(T\leq i\); otherwise, such that \(X ^ {\prime} _ i\in\lbrack G,X ^ {\prime} _ T\rbrack\) and \(i\leq T\).

By the constraints, \(X ^ {\prime} _ i\) is always monotonic with respect to \(X ^ {\prime} _ i\). Also, by the conditions of the values \(X ^ {\prime} _ i\), the cost to pay has a form of \(\displaystyle\sum _ {l\leq i\leq r}X ^ {\prime} _ i-G\times(r-l+1)\) or \(\displaystyle G\times(r-l+1)-\sum _ {l\leq i\leq r}X ^ {\prime} _ i\).

Therefore, the problem can be solved by the following approaches.

• Use a data structure like a lazy segment tree that supports segment assignment and segment sum, minimum value, and maximum value retrieval, to directly perform the operations above.
• Use a balanced binary tree like std::map to manage segments of indices, each having the same value of \(X ^ {\prime} _ i\).

Sample code follows below.

In this sample code, we use a lazy segment tree.

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

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

    // Create a segment tree
    auto segment_tree = [] (const auto N) {
        // (区間の長さ, 区間内の総和, 区間内の最小値, 区間内の最大値) を管理する
        // Manages (the length of segment, the sum of elements, the minimum value, the maximum value)
        struct segment_tree_value {
            unsigned length;
            unsigned long sum;
            unsigned min, max;
        };
        // Assignment into a segment
        using assign_type = optional<unsigned>;
        atcoder::lazy_segtree<segment_tree_value, [](const auto& lhs, const auto& rhs) -> segment_tree_value {
            // Merge segments nicely
            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 {
            // Identity element is a length-0 segment
            return {0U, 0UL, offset * 2, 0U};
        }, assign_type, [](const auto& f, const auto x) {
            // If there is an assignment query, fill with it
            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;

        // The current position is the sum, minimum, or maximum value, of the length-1 segment
        const auto now_position{segment_tree.get(T).max};
        if (now_position < G) { // if the destination is to the west:
            // enumerate persons to the east of the current position and to the west of the destination,
            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)};
            // and find the number of moves required
            ans += static_cast<unsigned long>(length) * G - sum;
            // Move all the persons in between
            segment_tree.apply(T, upper_bound, G);
        } else { // if the destination is to the east:
            // enumerate persons to the west of the current position and to the east of the destination,
            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)};
            // and find the number of moves required
            ans += sum - static_cast<unsigned long>(length) * G;
            // Move all the persons in between
            segment_tree.apply(it, T + 1, G);
        }
    }

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