#include
     
      #include
      
       #include
       
        #define N 50005using namespace std;int maxx[N][20],minn[N][20],a[N];int ST(int n){    for(int i=1;i<=n;i++)    {        maxx[i][0]=a[i];        minn[i][0]=a[i];    }    for(int j=1;(1<
        
         <=n;j++)    {        for(int i=1;i+(1<
         
          <=n;i++)        {            maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<(j-1))][j-1]);            minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);        }    }}int main(){    int n,q,lf,rg,mx,mn;    cin>>n>>q;    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);    }    ST(n);    for(int i=1;i<=q;i++)    {        scanf("%d %d",&lf,&rg);        int k=log2(rg-lf+1);        mx=max(maxx[lf][k],maxx[rg-(1<