#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int M = 1e5;

//n序列长度

//q次询问

int n,q;

//s是存放当前点的数值

//log预处理最多跳2的v次方(使得跳2^(v+1)超出范围,跳2^(v-1)次方之后两段的长度不够n)

int s[M],log[M];

//f存放区间最大值

int f[M][]; 

int main()

{

    //输入数据

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",&s[i]);

    //预处理log数组(log以2为底i的对数)

    for(int i=;i<=n;i++) log[i]=log[i>>]+;

    //自己往右跳一步就是自己

    for(int i=;i<=n;i++) f[i][]=s[i];

    for(int i=,k=;i<=log[n];i++,k*=)

    {//j+k-1是当前模拟到的左区间的右端点的长度下标

        for(int j=;j+k-<=n;j++)

        {

            f[j][i]=max(f[j][i-],f[j+k][i-]);

        }

    }

    //几组数据

    scanf("%d",&q);

    //跳的2的几次方

    int len;

    //左右端点

    int a,b;

    //记录答案

    int ans;

    for(int i=;i<=q;i++)

    {

        scanf("%d%d",&a,&b);

        a++,b++;//因为题目中数据是从0开始的,而我写的是从1开始的

        //+1的原因是因为右端点坐标减去左端点坐标得到的数不是该区间点的个数,可以自己画个图意会一下...

        len=log[b-a+];

        //减区间分为两段后,在其中找出的最大值就是该区间的最大值

        //1<<len就是2^len (减去2^len之后在图上多减去了一个点,将这个点加上,即为第二段的开始起点)

        ans=max(f[a][len],f[b-(<<len)+][len]);

        printf("%d\n",ans);

    }

    return ;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

const int M = ;

int n,m;

int a[M];//保存数

int f[M][];//f[i][j]表示第i个数向后  2的j次方  个数取得的最小值 

int main()

{

    cin>>n>>m;

    for(int i=;i<=n;++i) cin>>a[i];

    for(int i=;i<=n;++i) f[i][]=a[i];

    for(int j=;j<=;++j)

        for(int i=;i<=n;++i)

            if(i+(<<j)-<=n)

                f[i][j]=min(f[i][j-],f[i+(<<(j-))][j-]);//RMQ初始化

    int i,j;

    for(int x=;x<=n-m+;++x)

    {

        i=x,j=x+m-;

        int k=log(j-i+)/log();

        cout<<min(f[i][k],f[j-(<<k)+][k])<<endl;

    }

    return ;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

const int M = ;

int n,k,x,y;

int a[M];//保存数

int f1[M][];//f[i][j]表示第i个数向后  2的j次方  个数取得的最小值

int f2[M][],Maxx[M];//最大值 

int main()

{

    freopen("window.in","r",stdin);

    freopen("window.out","w",stdout);

    ios::sync_with_stdio(false);

    cin>>n>>k;

    for(int i=;i<=n;++i) cin>>a[i];

    for(int i=;i<=n;++i) f1[i][]=f2[i][]=a[i];

    for(int j=;j<=;++j)

        for(int i=;i<=n;++i)

            if(i+(<<j)-<=n)

                f1[i][j]=min(f1[i][j-],f1[i+(<<(j-))][j-]),//RMQ初始化

                f2[i][j]=max(f2[i][j-],f2[i+(<<(j-))][j-]);

    for(int i=;i<=n-k+;++i)

    {

        x=i,y=i+k-;

        int k=log(y-x+)/log();

        cout<<min(f1[x][k],f1[y-(<<k)+][k])<<" ";

        Maxx[i]=max(f2[x][k],f2[y-(<<k)+][k]);

    }

    cout<<endl;

    for(int i=;i<=n-k+;++i)

        cout<<Maxx[i]<<" ";

    return ;

}