#include "gap.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <iomanip>
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
const ll INF = 2e18;
const ll MOD = 1e9 + 7;
long long findGap(int T, int N) {
if (T == 1) {
ll last = 1e18 + 1, first = -1;
vll arr;
while (true) {
ll cur_first, cur_last;
MinMax(first + 1, last - 1, &cur_first, &cur_last);
if (cur_first == -1) break;
first = cur_first;
last = cur_last;
arr.push_back(cur_first);
arr.push_back(cur_last);
}
sort(arr.begin(), arr.end());
ll ans = 0;
rep(i, 0, arr.size() - 1) {
upmax(ans, arr[i + 1] - arr[i]);
}
return ans;
}
ll n = N;
ll first = -1, last = -1;
MinMax(0, 1e18, &first, &last);
ll L = (last - first);
ll x = (L + n - 2) / (n - 1);
ll last_finish = first;
ll ans = x;
for (ll i = first; i <= last; i += x + 1) {
ll cur_first = -1, cur_last = -1;
MinMax(i, i + x, &cur_first, &cur_last);
if (cur_first == -1) continue;
upmax(ans, cur_first - last_finish);
last_finish = cur_last;
}
return ans;
}
/*
2 4
2 3 6 8
*/
