const int N=2e5+10,M=log2(N);
int a[N];
int f[2][N][M];
void st()
{
    for(int j=0;(1<<j)<=n;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
            if(!j)f[0][i][j]=f[1][i][j]=a[i];
            else 
            {
                f[0][i][j]=max(f[0][i][j-1],f[0][i+(1<<(j-1))][j-1]);
                f[1][i][j]=min(f[1][i][j-1],f[1][i+(1<<(j-1))][j-1]);
            }
    }
}
int query(int l,int r,bool s)
{
    int len=r-l+1;
    int q=log2(len);
    if(s)return max(f[0][l][q],f[0][r-((1<<q)-1)][q]);
    else return min(f[1][l][q],f[1][r-((1<<q)-1)][q]);
}