#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;
}