#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
const int N=50005;
int n,m;
int a[N],dp_min[N][32],dp_max[N][32];
int LOG2[N];
void init(int n){
    for(int i=1;i<=n;i++){
        dp_min[i][0]=a[i];
        dp_max[i][0]=a[i];
    }
    int p=log2(n);
    for(int k=1;k<=p;k++){
        for(int s=1;s+(1<<k)-1<=n;s++){
            dp_min[s][k]=min(dp_min[s][k-1],dp_min[s+(1<<(k-1))][k-1]);
            dp_max[s][k]=max(dp_max[s][k-1],dp_max[s+(1<<(k-1))][k-1]);
        }
    }
}
int query(int L,int R){
    int k=log2(R-L+1);
    int mn=min(dp_min[L][k],dp_min[R-(1<<k)+1][k]);
    int mx=max(dp_max[L][k],dp_max[R-(1<<k)+1][k]);
    return mx-mn;
}
int main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    
    return 0;
}