This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <iostream>
#include "datastructure/sparse_table.hpp"
using S = int;
S op(S a, S b) {
return std::min(a, b);
}
int main() {
int n, q;
std::cin >> n >> q;
std::vector<S> a(n);
for (int i = 0; i < n; i++) std::cin >> a[i];
SparseTable<S, op> s(a);
while (q--) {
int l, r;
std::cin >> l >> r;
std::cout << s.prod(l, r) << '\n';
}
}
#line 1 "test/library-checker/staticrmq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <iostream>
#line 2 "datastructure/sparse_table.hpp"
#include <cassert>
#include <vector>
template <class S, S (*op)(S, S)>
struct SparseTable {
public:
SparseTable() {
}
SparseTable(const std::vector<S>& v)
: _n(int(v.size())), d(_n), ceil_log2(_n + 1) {
ceil_log2[0] = 0;
ceil_log2[1] = 0;
for (int i = 2; i <= _n; i++) ceil_log2[i] = ceil_log2[i >> 1] + 1;
for (int i = 0; i < _n; i++) {
d[i].resize(ceil_log2[_n] + 1);
d[i][0] = v[i];
}
for (int b = 0; b < ceil_log2[_n]; b++) {
for (int i = 0; i < _n; i++) {
if (i + (1 << (b + 1)) > _n) break;
d[i][b + 1] = op(d[i][b], d[i + (1 << b)][b]);
}
}
}
S prod(int l, int r) {
assert(r - l > 0);
int b = ceil_log2[r - l];
return op(d[l][b], d[r - (1 << b)][b]);
}
private:
int _n;
std::vector<std::vector<S>> d;
std::vector<int> ceil_log2;
};
#line 5 "test/library-checker/staticrmq.test.cpp"
using S = int;
S op(S a, S b) {
return std::min(a, b);
}
int main() {
int n, q;
std::cin >> n >> q;
std::vector<S> a(n);
for (int i = 0; i < n; i++) std::cin >> a[i];
SparseTable<S, op> s(a);
while (q--) {
int l, r;
std::cin >> l >> r;
std::cout << s.prod(l, r) << '\n';
}
}