1 #include <bits/stdc++.h> 2 using namespace std; 3  4 vector<int> A; 5 int dp[1000005][20]; 6  7 void RMQ_init () { 8     int n = A.size(); 9     for (int i = 0; i < n; ++ i) {10         dp[i][0] = A[i];11     }12     for (int j = 1; (1 << j) <= n; ++ j) {13         for (int i = 0; i + (1 << j) - 1 < n; ++ i) {14             dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);15         }16     }17 }18 19 int RMQ (int L, int R) {20     int k = 0;21     while ((1 << (k + 1)) <= R - L + 1) ++ k;22     return min(dp[L][k], dp[R - (1 << k) + 1][k]);23 }24 25 int main () {26     int n;27     while (~scanf ("%d", &n)) {28         int x, op_n;29         for (int i = 0 ; i < n; ++ i) {30             scanf ("%d", &x);31             A.push_back(x);32         }33         /*34         for (int i = 0; i < A.size() - 1; ++ i) {35             cout << A[i] << endl;36         }37         */38         RMQ_init ();39         int a, b;40         scanf ("%d", &op_n);41         for (int i = 0; i < op_n; ++ i) {42             scanf ("%d%d", &a, &b);43             printf ("%d\n", RMQ(a - 1, b - 1));44         }45     }46     return 0;47 }