#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100'000;
const ll INF = 1'000'000'000'000'000'000;
ll n, t, a[N + 10];
void readInput(int x, int y) {
t = x;
n = y;
}
pair<ll, ll> ask(ll s, ll t) {
ll a, b;
MinMax(s, t, &a, &b);
return {a, b};
}
ll calcMax() {
ll mx = 0;
for (int i = 1; i < n; i++)
mx = max(mx, a[i + 1] - a[i]);
return mx;
}
ll solve1() {
ll x = 0, y = INF;
for (int i = 1, j = n; i <= j; i++, j--) {
pair<ll, ll> p = ask(x, y);
x = p.first;
y = p.second;
a[i] = x;
a[j] = y;
x++;
y--;
//cout << i << ' ' << j << ": " << x << ' ' << y << endl;
}
return calcMax();
}
ll solve2() {
pair<ll, ll> p = ask(0, INF);
ll mn = p.first, mx = p.second;
ll len = mx - mn + 1;
vector<ll> vec;
for (int i = 0; i < len % n; i++)
vec.push_back((len + n - 1) / n);
while (vec.size() < n)
vec.push_back(len / n);
vector<pair<ll, ll>> all;
ll pnt = mn;
for (int i = 0; i < vec.size(); i++) {
pair<ll, ll> tmp;
if (i == 0) {
if (vec[i] == 1)
tmp = {mn, mn};
else {
pair<ll, ll> p = ask(pnt + 1, pnt + vec[i] - 1);
if (p.second == -1)
tmp = {mn, mn};
else
tmp = {mn, p.second};
}
}
else
tmp = ask(pnt, pnt + vec[i] - 1);
if (tmp.first != -1)
all.push_back(tmp);
pnt += vec[i];
}
ll ans = 0;
for (int i = 1; i < all.size(); i++)
ans = max(ans, all[i].first - all[i - 1].second);
return ans;
}
ll solve() {
if (t == 1)
return solve1();
return solve2();
}
long long findGap(int T, int N) {
readInput(T, N);
return solve();
}
