1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
int a[20][1000010];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[0][i]);
    int x=0,y;
    for(int i=1;i<=n;i<<=1) x++;
    for(int i=1,p=1;i<x;i++,p<<=1){
        for(int j=1;j+p<=n;j++){
            a[i][j]=a[i-1][j]>a[i-1][j+p]?a[i-1][j+p]:a[i-1][j];
        }
    }
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d %d",&x,&y);
        if(x==y) printf("%d\n",a[0][x]);
        else{
        int j,w;
        for(j=0,w=1;w+x<=y;j++,w<<=1);
        w>>=1;j--;
        printf("%d\n",a[j][x]>a[j][y-w+1]?a[j][y-w+1]:a[j][x]);
        }
    }
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX