Problem I - TeamsCode summer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int lg = 18;
const int Inf = 1e9 + 7;

struct SparseMin {
    vector<vector<int>> t;
    vector<int> l;
    SparseMin(vector<int> &a) {
        int n = a.size();
        t.resize(lg, vector (n, INT_MAX));
        l.resize(n + 1);
        for (int i = 2; i <= n; i++) {
            l[i] = l[i - 1];
            if (1 << (l[i] + 1) <= i) l[i]++;
        }
        t[0] = a;

        for (int i = 1; i < lg; i++) {
            for (int j = 0; j < n; j++) {
                t[i][j] = min(
                    t[i - 1][j],
                    t[i - 1][min(j + (1 << (i - 1)), n - 1)]
                );
            }
        }
    }
    int query (int sl,int sr) {
        int j = l[sr - sl];
        return min(t[j][sl], t[j][sr - (1 << j)]);
    }
};

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

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (auto &a: A) cin >> a;

    A.push_back(Inf);

    vector up(N + 1, vector<int>(lg, N));
    vector mi(N + 1, vector<int>(lg, Inf));

    stack<int> ne;
    ne.emplace(N);

    map<int, int> mp;
    vector<int> neq(N, N);

    for (int i = N - 1; i >= 0; i--) {
        if (mp.count(A[i])) {
            neq[i] = mp[A[i]];
        }
        mp[A[i]] = i;
        while (A[ne.top()] <= A[i]) ne.pop();
        up[i][0] = ne.top();
        mi[i][0] = A[i] - up[i][0];
        ne.emplace(i);
    }

    SparseMin st(neq);

    for (int j = 1; j < lg; j++) {
        for (int i = 0; i < N; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
            mi[i][j] = min(
                mi[i][j - 1],
                mi[up[i][j - 1]][j - 1]
            );
        }
    }

    while (Q--) {
        int l, r;
        cin >> l >> r;
        l--;
        r = min(r, st.query(l, r));
        int ans = A[l] - 1;
        int i = l;
        for (int j = lg - 1; j >= 0; j--) {
            if (up[i][j] <= r) {
                ans = min(ans, l + mi[i][j]);
                i = up[i][j];
            }
        }
        ans = min(ans, A[i] - (r - l));
        cout << ans << '\n';
    }

}