#include "gap.h"
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
ll findGap(int T, int N) {
if (T == 1) {
// 1-Subtask: Har safar chetki elementlarni topib, oraliqni toraytiramiz
ll mn_val, mx_val;
ll l = 0, r = 1e18;
vector<ll> a(N);
int i = 0, j = N - 1;
while (i <= j) {
MinMax(l, r, &mn_val, &mx_val);
a[i++] = mn_val;
a[j--] = mx_val;
l = mn_val + 1;
r = mx_val - 1;
}
ll max_diff = 0;
for (int k = 0; k < N - 1; k++) {
max_diff = max(max_diff, a[k+1] - a[k]);
}
return max_diff;
} else {
// 2-Subtask: Oraliqni teng bo'laklarga bo'lib, maksimal farqni qidiramiz
ll mn_all, mx_all;
MinMax(0, 1e18, &mn_all, &mx_all);
ll L = mn_all, R = mx_all;
// Kamida (R-L)/(N-1) masofa bo'lishi aniq
ll block_size = (R - L + N - 2) / (N - 1);
ll max_diff = block_size;
ll last_val = mn_all;
for (ll i = L + 1; i < R; i += block_size + 1) {
ll cur_mn, cur_mx;
// Har bir blokdan faqat min va max ni olamiz
MinMax(i, min(i + block_size, R - 1), &cur_mn, &cur_mx);
if (cur_mn != -1) {
max_diff = max(max_diff, cur_mn - last_val);
last_val = cur_mx;
}
}
max_diff = max(max_diff, R - last_val);
return max_diff;
}
}
