#include <bits/stdc++.h>
#include "gap.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
ll findGap(int T, int N) {
vector<ll> A(N + 2);
A[0] = -1ll, A[N + 1] = 1000000000ll * 1000000000ll + 1ll;
for(ll l = 1; l <= (N + 1) / 2; l++) {
MinMax(A[l - 1] + 1, A[N - l + 2] - 1, &A[l], &A[N - l + 1]);
}
ll res = 0;
for(ll l = 2; l <= N; l++)
res = max(res, A[l] - A[l - 1]);
return res;
}
