#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;
long long findGap(int subtask, int N){
int lInd = 1;
int rInd = N;
std::vector< ll > a( N + 2 );
a[0] = -1;
a[N+1] = ll(1e18 + 1LL );
while( lInd < rInd ){
MinMax( a[lInd-1] +1, a[rInd+1]-1, &a[lInd], &a[rInd] );
cerr << out( lInd ) << out( rInd ) << out( a[lInd] ) << out( a[rInd] ) << endl;
lInd ++;
rInd --;
}
if( N & 1 ){
int m = (N/2) + 1;
ll trash;
MinMax( a[m-1] +1, a[m+1]-1, &a[m], &trash );
}
ll nas = 0;
for( int i=1 ; i < N ; i++ ){
cerr << out( i ) << out( a[i] ) << endl;
chkmax( nas, (ll)( a[i+1] - a[i] ) );
}
cerr << out( nas ) << endl;
return nas;
}
