RMQ

#include <bits/stdc++.h>

#define endl "\n"

using namespace std;

int n;

int a[100000], lg[100000], mn[100000][100000];

int rmq(int l, int r)
{
    int t = lg[r-l];
    return min(mn[l][t], mn[r-(1<<t)][t]);
}

signed main()
{
    cin >> n;
    for (int i=0; i<n; i++) cin >> a[i];
    for (int i=0; i<int(log(n)); i++)
    {
        for (int j=(1<<i); j<n; j++)
        {
            lg[j] = i;
        }
    }
    for (int i=n-1; i>=0; i--)
    {
        mn[i][0] = a[i];
        for (int j=0; j<int(log(n))-1; j++)
        {
            mn[i][j+1] = min(mn[i][j], mn[i+(1<<j)][j]);
        }
    }
    int m;
    cin >> m;
    for (int i=0; i<m; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << rmq(l, r) << " ";
    }
    return 0;
}