#include <iostream>
#include <climits>
#include <vector>
// Function prototype for provided MinMax function
void MinMax(long long s, long long t, long long* mn, long long* mx);
long long findGap(int T, int N) {
if (T != 1) {
// Only implementing subtask 1
return -1;
}
long long globalMin, globalMax;
MinMax(LONG_LONG_MIN, LONG_LONG_MAX, &globalMin, &globalMax);
if (N == 1) {
// If there is only one number, no gap exists
return 0;
}
// Calculate optimal number of segments
long long segmentSize = (globalMax - globalMin) / (N - 1);
long long maxGap = 0;
long long lastMax = globalMin;
// Process each segment to find the largest gap
for (long long i = 0; i < N - 1; ++i) {
long long s = globalMin + i * segmentSize + 1; // Start of the next segment
long long t = s + segmentSize - 1; // End of the next segment
if (i == N - 2) t = globalMax; // Ensure the last segment reaches globalMax
long long mn, mx;
MinMax(s, t, &mn, &mx);
if (mn != -1) { // If there are numbers in this range
maxGap = std::max(maxGap, mn - lastMax);
lastMax = mx;
}
}
return maxGap;
}
