sparse table done

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100010,logm=20;
unsigned int spx[logm][maxn],spi[logm][maxn];
int main(){
    int n,q,l,r;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>spi[0][i],spx[0][i]=spi[0][i];
    for(int i=1;i<logm;i++){ //O(n log n) building
        for(int j=1;j<=n;j++){
            if( j+ (1<<i-1)>n ){
                spx[i][j]=spx[i-1][j];
                spi[i][j]=spi[i-1][j];
                continue;
            }
            spx[i][j]=max(spx[i-1][j],spx[i-1][j+ (1<<i-1) ]);

            if(spi[i-1][j+ (1<<i-1) ]==0){
                spi[i][j]=spi[i-1][j];
                continue;
            }
            spi[i][j]=min(spi[i-1][j],spi[i-1][j+ (1<<i-1) ]);
        }
    }
    for(int i=0;i<q;i++){ //O(1) query
        int j=0,ans=0;
        cin>>l>>r;
        for(;j<logm;j++)if(r-l+1 < 1<<j){j--;break;}//int logm=18 for good reason

        ans+=max(spx[j][l],spx[j][r+1- (1<<j) ])-min(spi[j][l],spi[j][r+1- (1<<j) ]);
        cout<<ans<<"\n";
    }

    /*for(int i=0;i<logm;i++){
        for(int j=1;j<=n;j++)cout<<spx[i][j]<<"\t";
        cout<<"\n";
    }*/
    return 0;
}