#include <algorithm>
#include <exception>
#include <random>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define out( x ) #x << " = " << x << " "
#define endl "\n"
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
typedef long long ll;
const ll mod = 1e9 +7;
const int MAX_N = 1e6 + 42;
ll a[MAX_N];
long long findGap(int subtask, int n){
if( subtask == 1 ){
ll lInd = 0;
ll rInd = n-1;
ll mn=0;
ll mx=1e18;
while( lInd <= rInd ){
MinMax( mn, mx, &a[lInd ++],&a[rInd --]);
mn = a[lInd-1]+1;
mx = a[rInd+1]-1;
}
ll nas = 0;
for( int i=0 ; i < n-1 ; i++ ){
cerr << out( i ) << out( a[i+1] - a[i] ) << endl;
chkmax( nas, ll( a[i+1] - a[i] ) );
}
cerr << out( nas ) << endl;
return nas;
}else{
ll fir, lst;
MinMax( -1, 1e18, &fir, &lst );
std::set< ll > s;
s.insert( fir );
s.insert( lst );
ll gap = ( lst - fir ) / ( n - 1 );
if( gap == 0 ) return -1;
cerr << out( gap ) << endl;
for( ll j=fir+1 ; j < lst ; j += gap +1 ){
ll mn, mx;
MinMax( j, j + gap, &mn, &mx );
if( mn != -1 ) s.insert( mn );
if( mx != -1 ) s.insert( mx );
}
ll nas = -1;
for( auto it = s.begin() ; next( it ) != s.end() ; it++ ){
ll currNas = *(next( it ) ) - *it;
chkmax( nas, currNas );
}
cerr << out( nas ) << endl;
return nas;
}
}
