Problem I Segment Tree

#include <algorithm>
#include <cstdint>
#include <ios>
#include <iostream>
#include <map>
#include <numeric>
#include <utility>
#include <vector>

namespace segment_tree {

    constexpr std::int32_t log_2(std::int32_t);

    template <typename F>
    void for_pars(std::int32_t nd, std::int32_t dir, F f) {

        const std::int32_t lvls = log_2(nd);

        for (std::int32_t i = 1; i <= lvls; ++i) {
            f(nd >> (dir == 0 ? lvls - i + 1 : i));
        }

    }

    template <typename F>
    void for_rng(std::int32_t nd_l, std::int32_t nd_r, F f) {

        while (nd_l < nd_r) {
            if (nd_l & 1) {
                f(nd_l);
                ++nd_l;
            }
            if (nd_r & 1) {
                --nd_r;
                f(nd_r);
            }
            nd_l >>= 1;
            nd_r >>= 1;
        }

    }

    template <typename F>
    void for_rng_ord(std::int32_t nd_l, std::int32_t nd_r, F f) {

        if (nd_r - nd_l <= 0) {
            return;
        }

        const std::int32_t msk = (1 << log_2((nd_l - 1) ^ nd_r)) - 1;

        std::int32_t nd = -nd_l & msk;

        while (nd) {
            const std::int32_t bit = __builtin_ctz(nd);
            f(((nd_l - 1) >> bit) + 1);
            nd ^= 1 << bit;
        }

        nd = nd_r & msk;

        while (nd) {
            const std::int32_t bit = log_2(nd);
            f((nd_r >> bit) - 1);
            nd ^= 1 << bit;
        }

    }

    constexpr std::int32_t log_2(std::int32_t x) {

        return 31 - __builtin_clz(x);

    }

}

template <typename F>
class y_combinator {

private:

    F f;

public:

    explicit y_combinator(F&& f) : f(f) {}

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const {

        return f(*this, std::forward<Args>(args)...);

    }

};

template <typename F>
y_combinator(F) -> y_combinator<F>;

void solve() {

    std::int32_t n;
    std::int32_t q;

    std::cin >> n >> q;

    std::vector<std::int32_t> a(n);

    for (auto& x : a) {
        std::cin >> x;
    }

    const std::int32_t inf = *std::max_element(std::begin(a), std::end(a)) + n;
    std::map<std::int32_t, std::int32_t> nxts;
    const std::int32_t seg_sz = 1 << segment_tree::log_2(n * 2 - 1);

    std::vector seg(seg_sz * 2, inf);
    std::vector seg_apps(seg_sz * 2, inf);
    std::vector seg_bnds(seg_sz * 2, n);
    std::vector<std::int32_t> seg_idxs(seg_sz * 2);
    std::vector<std::int32_t> seg_mxs(seg_sz * 2);
    std::vector<std::int32_t> szs(seg_sz * 2);

    std::copy(std::begin(a), std::end(a), std::begin(seg_mxs) + seg_sz);

    for (std::int32_t i = 0; i < n; ++i) {
        seg[seg_sz + i] = a[i] - i;
    }

    std::iota(std::begin(seg_idxs) + seg_sz, std::end(seg_idxs), 0);

    std::fill_n(std::begin(szs) + seg_sz, n, 1);

    for (std::int32_t i = n - 1; i >= 0; --i) {
        if (nxts.count(a[i])) {
            seg_bnds[seg_sz + i] = nxts[a[i]];
        }
        nxts[a[i]] = i;
    }

    const auto apply = [&](std::int32_t nd, std::int32_t mx) -> std::int32_t {
        if (seg_mxs[nd] <= mx) {
            return mx - seg_idxs[nd];
        }
        std::int32_t res = inf;
        y_combinator(
            [&](auto self, std::int32_t seg_nd) -> void {
                if (seg_nd >= seg_sz) {
                    res = std::min(res, seg[seg_nd]);
                    return;
                }
                const std::int32_t nd_l = seg_nd << 1;
                const std::int32_t nd_r = seg_nd << 1 | 1;
                if (seg_mxs[nd_l] > mx) {
                    self(nd_l);
                    res = std::min(res, seg_apps[seg_nd]);
                } else {
                    res = std::min(res, mx - seg_idxs[nd_l]);
                    self(nd_r);
                }
            }
        )(nd);
        return res;
    };

    for (std::int32_t i = seg_sz - 1; i; --i) {
        seg_mxs[i] = std::max(seg_mxs[i << 1], seg_mxs[i << 1 | 1]);
        seg_idxs[i] = seg_idxs[i << 1 | 1];
        szs[i] = szs[i << 1] + szs[i << 1 | 1];
        seg_apps[i] = apply(i << 1 | 1, seg_mxs[i << 1]);
        seg[i] = std::min(seg[i << 1], seg_apps[i]);
        seg_bnds[i] = std::min(seg_bnds[i << 1], seg_bnds[i << 1 | 1]);
    }

    for (std::int32_t i = 0; i < q; ++i) {
        std::int32_t l;
        std::int32_t r;
        std::cin >> l >> r;
        --l;
        --r;
        std::int32_t bnd = r + 1;
        std::int32_t mx = 0;
        std::int32_t val;
        segment_tree::for_rng(
            seg_sz + l, seg_sz + r + 1,
            [&](std::int32_t nd) -> void {
                bnd = std::min(bnd, seg_bnds[nd]);
            }
        );
        segment_tree::for_rng_ord(
            seg_sz + l, seg_sz + bnd,
            [&](std::int32_t nd) -> void {
                if (mx) {
                    val = std::min(val, apply(nd, mx));
                } else {
                    val = seg[nd];
                }
                mx = std::max(mx, seg_mxs[nd]);
            }
        );
        val += l - 1;
        std::cout << val << '\n';
    }

}

int main() {

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    solve();

    return 0;

}