Codeforces Round #397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined)

#include <bits/stdc++.h>

using i64 = long long;

template<class Info,
    class Merge = std::plus<Info>>
struct SegmentTree {
    const int n;
    const Merge merge;
    std::vector<Info> info;
    SegmentTree(int n) : n(n), merge(Merge()), info(4 << std::__lg(n)) {}
    SegmentTree(std::vector<Info> init) : SegmentTree(init.size()) {
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = merge(info[2 * p], info[2 * p + 1]);
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p + 1, m, r, x, y));
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
};
 
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n = 0) {
        init(n);
    }
    
    void init(int n) {
        this->n = n;
        a.assign(n, T());
    }
    
    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    }
    
    T sum(int x) {
        auto ans = T();
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int kth(T k) {
        int x = 0;
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && k >= a[x + i - 1]) {
                x += i;
                k -= a[x - 1];
            }
        }
        return x;
    }
};
 
struct Max {
    int x;
    Max(int x = -1) : x(x) {}
};
 
Max operator+(const Max &a, const Max &b) {
    return std::max(a.x, b.x);
}
 
constexpr int inf = 1E9;
struct Min {
    int x;
    Min(int x = inf) : x(x) {}
 
    Min &operator+=(Min a) {
        x = std::min(a.x, x);
        return *this;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> a(n);

    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    auto b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    const int N = b.size();

    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    }

    int m;
    std::cin >> m;
    std::vector<std::vector<std::pair<int, int>>> qry(n);

    for (int i = 0; i < m; i++) {
        int l, r;
        std::cin >> l >> r;
        l--, r--;
        qry[r].emplace_back(l, i);
    }

    SegmentTree<Max> seg(N);
    Fenwick<Min> fen(n);
    std::vector<int> ans(m);

    seg.modify(a[0], 0);
    for (int i = 1; i < n; i++) {
        int j = seg.rangeQuery(a[i], N).x;
        while (j != -1) {
            fen.add(n - 1 - j, b[a[j]] - b[a[i]]);

            if (a[j] == a[i]) {
                break;
            }

            int num = lower_bound(b.begin(), b.end(), (b[a[j]] + b[a[i]]) / 2 + 1) - b.begin();
            j = seg.rangeQuery(a[i], num).x;
        }
 
        int k = seg.rangeQuery(0, a[i] + 1).x;
        while (k != -1) {
            fen.add(n - 1 - k, b[a[i]] - b[a[k]]);

            if (a[k] == a[i]){
                break;
            }

            int num = lower_bound(b.begin(), b.end(), (b[a[k]] + b[a[i]] + 1) / 2) - b.begin();
            k = seg.rangeQuery(num, a[i] + 1).x;
        }
 
        seg.modify(a[i], i);
        
        for (auto &[l, j] : qry[i]) {
            ans[j] = fen.sum(n - l).x;
        }
    }    
 
    for (int i = 0; i < m; i++) {
        std::cout << ans[i] << '\n';
    }

    return 0;
}