#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back
// const ll NUM_BUCKETS = 10ll;
vll div_buckets(ll w, ll k) {
ll base_bucket_size = w / k;
ll num_buckets_increase = w % k;
vll res(k, base_bucket_size);
for(ll i = 0ll; i < num_buckets_increase; i++) {
res[i]++;
}
return res;
}
void solve_t2(vll& nums, ll l, ll r, ll N, ll NUM_BUCKETS) {
if(((ll)nums.size()) >= N) return;
if(r - l + 1ll <= 0ll) return;
ll mn, mx;
MinMax(l, r, &mn, &mx);
if(mn == -1ll) return;
if(mx > mn) {
nums.pb(mn);
nums.pb(mx);
ll nl = mn + 1ll, nr = mx - 1ll;
ll w = nr - nl + 1ll;
if(w <= 0ll) return;
vll buckets = div_buckets(w, NUM_BUCKETS);
ll cur_l = nl;
for(ll i = 0ll; i < NUM_BUCKETS; i++) {
solve_t2(nums, cur_l, cur_l + buckets[i] - 1ll, N, NUM_BUCKETS);
cur_l += buckets[i];
}
} else {
nums.pb(mn);
return;
}
}
void solve_t1(vll& nums, ll l, ll r, ll N) {
if(((ll)nums.size()) >= N) return;
if(r - l + 1ll <= 0ll) return;
ll mn, mx;
MinMax(l, r, &mn, &mx);
if(mn == -1ll) return;
if(mx > mn) {
nums.pb(mn);
nums.pb(mx);
solve_t1(nums, mn + 1ll, mx - 1ll, N);
} else {
nums.pb(mn);
return;
}
}
ll findGap(int T, int N)
{
vll ans;
if(T == 2) {
solve_t2(ans, 0ll, 1000000000000000000ll, N, min(20ll, (ll)N));
} else {
solve_t1(ans, 0ll, 1000000000000000000ll, N);
}
sort(ans.begin(), ans.end());
// for(int i = 0; i < N; i++) {
// cerr << ans[i] << " ";
// }
// cerr << endl;
ll maxgap = 0ll;
for(int i = 0; i < N - 1; i++) {
maxgap = max(maxgap, ans[i + 1] - ans[i]);
}
return maxgap;
}
