#include "gap.h"
#include <algorithm>
#define MAX_N 100000
#define MAX_A 1000000000000000000
int A[MAX_N];
long long findGap(int T, int N) {
long long min, max, ans = 0;
if (T == 1) { // subtask 1
int t = (N + 1) / 2, low = 0, high = N;
min = -1, max = MAX_A + 1;
for(int i = 0; i < t; i++) {
MinMax(min + 1, max - 1, &min, &max);
A[low++] = min;
A[--high] = max;
}
for(int i = 1; i < N; i++)
if(ans < A[i] - A[i - 1])
ans = A[i] - A[i - 1];
}
else { // subtask 2
MinMax(0, MAX_A, &min, &max);
long long gap = (max - min) / N, x, y;
int M = 0, done = min, next;
A[M++] = min;
while(done + 1 < max) {
x = y = -1;
next = std::min(done + 1 + gap, max - 1);
MinMax(done + 1, next, &x, &y);
if(x != -1) {
A[M++] = x;
if(x < y) A[M++] = y;
}
done = next;
}
A[M++] = max;
for(int i = 0; i < M; i++)
if(ans < A[i] - A[i - 1])
ans = A[i] - A[i - 1];
}
return ans;
}
