#include "gap.h"
#include <vector>
#include <algorithm>
typedef long long int ll;
using namespace std;
pair<ll, ll> MinMax(ll v1, ll v2) {
ll vv1, vv2;
MinMax(v1, v2, &vv1, &vv2);
return make_pair(vv1, vv2);
}
long long findGap(int T, int N)
{
ll ans = 1;
pair<ll, ll> cv = MinMax(0, 1000000000000000000);
for (int i = 1; i < N / 2; i++) {
pair<ll, ll> nv = MinMax(cv.first + 1, cv.second - 1);
ans = max({ ans,nv.first - cv.first,cv.second - nv.second });
cv = nv;
}
if (N % 2 == 1) {
pair<ll, ll> nv = MinMax(cv.first + 1, cv.second - 1);
ans = max({ ans,nv.first - cv.first,cv.second - nv.second });
cv = nv;
}
else ans = max(ans, cv.second - cv.first);
return ans;
}
