#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
ll a[maxn];
extern "C" void MinMax(long long, long long, long long *, long long *);
extern "C" long long findGap(int T, int n){
	ll ans=0; ll l=1,r=n; ll l1,r1,lst;
	MinMax(0,1e18,&a[l],&a[r]);
	if(T==1){
		while(l+1<r){
			MinMax(a[l]+1,a[r]-1,&a[l+1],&a[r-1]);
			l++; r--;
		}
		for(int i=1;i<n;i++) ans=max(ans,a[i+1]-a[i]);
	}else{
		ll B=(a[n]-a[1])/(n-1); if((a[n]-a[1])%(n-1)) B++; lst=a[1];
		for(ll i=a[1]+1;i<=a[n]-1;i+=B){
			r=min(i+B-1,a[n]-1); l=i;
			MinMax(l,r,&l1,&r1);
			ans=max(ans,l1-lst); if(r1>0) lst=r1;
		}
		ans=max(ans,a[n]-lst);
	}
	return ans;
}

/usr/bin/ld: /tmp/ccfED1xT.o: in function `main':
implementer.cpp:(.text.startup+0x1c6): undefined reference to `findGap(int, int)'
/usr/bin/ld: /tmp/ccF4BcXU.o: in function `findGap':
answer.code:(.text+0x50): undefined reference to `MinMax'
/usr/bin/ld: answer.code:(.text+0xcf): undefined reference to `MinMax'
/usr/bin/ld: answer.code:(.text+0x16c): undefined reference to `MinMax'
collect2: error: ld returned 1 exit status