#include <algorithm>
#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;
struct Node{
ll fir;
ll lst;
ll nas;
};
Node merge( const Node& a, const Node& b ){
Node nas;
nas.fir = a.fir;
if( a.fir == -1 ) nas.fir = b.fir;
nas.lst = b.lst;
if( b.lst == -1 ) nas.lst = a.lst;
ll currNas = b.fir - a.lst;
if( b.fir == -1 || a.lst == -1 ) currNas = 0;
cerr << out( currNas ) << endl;
nas.nas = std::max({ a.nas, b.nas, currNas });
cerr << out( a.fir ) << out( a.lst ) << out( a.nas ) << endl;
cerr << out( b.fir ) << out( b.lst ) << out( b.nas ) << endl;
cerr << out( nas.fir ) << out( nas.lst ) << out( nas.nas ) << endl << endl;
return nas;
}
struct Node sol( ll l, ll r ){
ll mn, mx;
MinMax( l, r, &mn, &mx );
cerr << out( l ) << out( r ) << out( mn ) << out( mx ) << endl;
if( mn == mx ){
Node ret;
ret.nas = -1;
ret.fir = ret.lst = mn;
return ret;
}
ll m = ( l + r ) >> 1;
Node left = sol( l, m );
Node right = sol( m+1, r );
return merge( left, right );
}
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 );
Node nas = sol( fir-1, lst+1 );
cerr << out( nas.fir ) << out( nas.lst ) << out( nas.nas ) << endl;
return nas.nas;
}
}
