#include <bits/stdc++.h>
using namespace std;
void MinMax(int s, int t, long long &mn, long long &mx);
long long findGap(int T, int n) {
vector<long long> a(n + 1);
long long mn[2], mx[2];
int i;
for(i = 1; i + 2 <= n; i += 3) {
MinMax(i, i + 1, mn[0], mx[0]);
if(mn[0] == mx[0]) {
a[i] = a[i + 1] = mn[0];
i --; continue;
} else {
MinMax(i + 1, i + 2, mn[1], mx[1]);
if(mn[1] == mx[1]) {
a[i + 1] = a[i + 2] = mn[1];
a[i] = mn[0] + mx[0] - mn[1];
} else {
if(mn[0] == mn[1] || mn[0] == mx[1]) {
a[i + 1] = mn[0];
} else a[i + 1] = mx[0];
a[i] = mn[0] + mx[0] - a[i + 1];
a[i + 2] = mn[1] + mx[1] - a[i + 1];
}
}
}
if(i + 1 == n) {
MinMax(i, i, mn[0], mx[0]);
a[i] = mn[0];
MinMax(i + 1, i + 1, mn[0], mx[0]);
a[i + 1] = mn[0];
} else if(i == n) {
MinMax(i, i, mn[0], mx[0]);
a[i] = mn[0];
}
long long r = a[2] - a[1];
for(int i = 3; i <= n; i ++)
r = max(r, a[i] - a[i - 1]);
return r;
}