1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <string> 5 #include <cstdio> 6 #include <cmath> 7 #define MAXN 2222222 8 #define MAXM 11111 9 #define lch(x) x<<110 #define rch(x) x<<1|111 #define lson l,m,rt<<112 #define rson m+1,r,rt<<1|113 using namespace std;14 int mi[MAXN][22], mx[MAXN][22], w[MAXN];15 int n, q;16 void rmqinit()17 {18     for(int i = 1; i <= n; i++) mi[i][0] = mx[i][0] = w[i];19     int m = (int)(log(n * 1.0) / log(2.0));20     for(int i = 1; i <= m; i++)21         for(int j = 1; j <= n; j++)22         {23             mx[j][i] = mx[j][i - 1];24             if(j + (1 << (i - 1)) <= n) mx[j][i] = max(mx[j][i], mx[j + (1 << (i - 1))][i - 1]);25             mi[j][i] = mi[j][i - 1];26             if(j + (1 << (i - 1)) <= n) mi[j][i] = min(mi[j][i], mi[j + (1 << (i - 1))][i - 1]);27         }28 }29 int rmqmin(int l,int r)30 {31     int m = (int)(log((r - l + 1) * 1.0) / log(2.0));32     return min(mi[l][m] , mi[r - (1 << m) + 1][m]);33 }34 int rmqmax(int l,int r)35 {36     int m = (int)(log((r - l + 1) * 1.0) / log(2.0));37     return max(mx[l][m] , mx[r - (1 << m) + 1][m]);38 }39 int main()40 {41     scanf("%d", &n);42     for(int i = 1; i <= n; i++) scanf("%d", &w[i]);43     rmqinit();44     int l, r;45     scanf("%d",&q);46     while(q--)47     {48         scanf("%d%d", &l, &r);49         printf("%d\n", rmqmin(l, r));50     }51     return 0;52 }