#include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 int a[];

 int lg;

 int min1[][],max1[][],n,q;

 void rmq(int n){

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

         for(int i=;i+(<<j)-<=n;i++){

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

             min1[i][j]=min(min1[i][j-],min1[i+(<<(j-))][j-]);

         }

     }

 }

 int main(){

     int n,q;

     ios::sync_with_stdio();

     cin.tie();

     cout.tie();

     cin>>n>>q;

     lg=int(log10(n)/log10());

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

     rmq(n);

     while(q--){

         int a,b;

         cin>>a>>b;

         if(a>b) swap(a,b);

         int k=(int)(log10(b-a+)/log10(2.0));

         int maxres=max(max1[a][k],max1[b-(<<k)+][k]);

         int minres=min(min1[a][k],min1[b-(<<k)+][k]);

         cout<<maxres-minres<<"\n";

     }

 }