#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class RMQ {
private:
vector<int> arr;
vector<int> block_min;
int block_size;
public:
RMQ(const vector<int>& input) {
arr = input;
int n = arr.size();
block_size = static_cast<int>(sqrt(n)) + 1;
block_min.resize(block_size, INT_MAX);
for (int i = 0; i < n; ++i)
block_min[i / block_size] = min(block_min[i / block_size], arr[i]);
}
int query(int l, int r) {
int min_val = INT_MAX;
while (l <= r && l % block_size != 0) {
min_val = min(min_val, arr[l]);
++l;
}
while (l + block_size - 1 <= r) {
min_val = min(min_val, block_min[l / block_size]);
l += block_size;
}
while (l <= r) {
min_val = min(min_val, arr[l]);
++l;
}
return min_val;
}
};
int main() {
vector<int> input = {7, 2, 3, 0, 5, 10, 3, 12};
RMQ rmq(input);
cout << "Minimum in range [1, 5]: " << rmq.query(1, 5) << endl;
cout << "Minimum in range [2, 7]: " << rmq.query(2, 7) << endl;
cout << "Minimum in range [0, 3]: " << rmq.query(0, 3) << endl;
return 0;
}