#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#include "gap.h"
set<ll> S;
ll subtask1(int N) {
//cerr << N << endl;
ll l = 0, r = 1e18+1;
ll q, w;
while (N > 0) {
MinMax(l, r, &q, &w);
//cerr << q << w << endl;
S.insert(q); S.insert(w);
l = q+1;
r = w-1;
N -= 2;
}
set<ll>::iterator it = S.begin();
it++;
ll best = 0;
for (; it != S.end(); it++) {
set<ll>::iterator it2 = it;
it2--;
best = max(best, (*it) - (*it2));
}
return best;
}
ll subtask2(int N) {
return 1337;
}
long long findGap(int T, int N)
{
if (T == 1) return subtask1(N);
else return subtask2(N);
}
