This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <iostream>
#include <limits>
#include "../../data_type/min_monoid.hpp"
#include "../../sparse_table/sparse_table.hpp"
using namespace std;
using llong = long long;
llong n, q;
vector<llong> a;
int main() {
cin >> n >> q;
a.resize(n);
for (auto &v : a) cin >> v;
SparseTable<MinMonoid<llong>> rmq(a.begin(), a.end());
while (q--) {
llong l, r;
cin >> l >> r;
cout << rmq.fold(l, r) << '\n';
}
return 0;
}
#line 1 "test/yosupo/static_rmq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <iostream>
#include <limits>
#line 1 "data_type/min_monoid.hpp"
#include <algorithm>
#line 6 "data_type/min_monoid.hpp"
#include <numeric>
//===
template <class T>
struct MinMonoid {
using value_type = T;
inline static T identity() {
return std::numeric_limits<T>::max();
};
inline static T operation(const T a, const T b) {
return std::min(a, b);
};
};
//===
#line 1 "sparse_table/sparse_table.hpp"
#include <functional>
#include <iterator>
#include <vector>
//===
template <class SemiLattice>
struct SparseTable {
using S = SemiLattice;
using T = typename SemiLattice::value_type;
std::vector<std::vector<T>> table;
std::vector<size_t> log2;
SparseTable() = default;
template <class InputItr>
SparseTable(InputItr first, InputItr last) {
int n = std::distance(first, last);
log2.assign(n + 1, 0);
for (int i = 2; i <= n; i++) log2[i] = log2[i / 2] + 1;
table.reserve(log2[n] + 1);
table.emplace_back(first, last);
for (int i = 1; (1 << i) <= n; i++) {
int w = 1 << (i - 1);
table.emplace_back();
table.back().reserve(n - (1 << i) + 1);
for (int j = 0; j + (1 << i) <= n; j++) {
table[i].emplace_back(
S::operation(table[i - 1][j], table[i - 1][j + w]));
}
}
};
//[l, r)
T fold(int l, int r) {
int k = log2[r - l];
return S::operation(table[k][l], table[k][r - (1 << k)]);
};
int size() {
return table[0].size();
};
T operator[](const int k) {
return table[0][k];
};
};
//===
#line 8 "test/yosupo/static_rmq.test.cpp"
using namespace std;
using llong = long long;
llong n, q;
vector<llong> a;
int main() {
cin >> n >> q;
a.resize(n);
for (auto &v : a) cin >> v;
SparseTable<MinMonoid<llong>> rmq(a.begin(), a.end());
while (q--) {
llong l, r;
cin >> l >> r;
cout << rmq.fold(l, r) << '\n';
}
return 0;
}