#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 + (ll)1, first = -1;
set<ll> arr;
ll n = N;
while (true) {
ll cur_first, cur_last;
if (first == -1) MinMax(first + 1, 1e18, &cur_first, &cur_last);
else MinMax(first + 1, last - 1, &cur_first, &cur_last);
if (cur_first == -1) break;
first = cur_first;
last = cur_last;
arr.insert(cur_first);
arr.insert(cur_last);
if (arr.size() == n) break;
}
vll a;
for (auto& it : arr) {
a.push_back(it);
}
ll ans = 0;
rep(i, 0, a.size() - 1) {
upmax(ans, a[i + 1] - a[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
*/
