#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;
long long findGap(int subtask, int n){
std::vector< ll > a;
ll mn = -1;
ll mx = 1e18 + 2LL;
while( (ll)a.size() < n ){
MinMax(mn + 1, mx - 1, &mn, &mx);
if (mn != mx) {
if( (ll)a.size() + 2 <= n ){
a.push_back(mn);
a.push_back(mx);
}else a.push_back(mn);
}else a.push_back(mn);
}
std::sort( a.begin(), a.end() );
//for( auto j : a ) cerr << j << " ";
//cerr << endl;
ll nas = -1;
for( int i=0 ; i < (ll)a.size() - 1 ; i++ ) chkmax( nas, (ll)(a[i+1] - a[i]) );
cerr << out( nas ) << endl;
return nas;
}
