#include "gap.h"
#include <bits/stdc++.h>

using namespace std;

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;
}