#include "gap.h"
#include <stdio.h>
long long arr[100001];
long long findGap(int T, int N)
{
if(T == 1) {
long long min = 0;
long long max = 1e18;
int minIdx = 0;
int maxIdx = N-1;
int maxIter = (N+1)/2;
long long low;
long long high;
for(int i = 0; i < maxIter; i++) {
MinMax(min, max, &low, &high);
arr[minIdx++] = low;
arr[maxIdx--] = high;
min = low+1;
max = high-1;
}
long long result = 0;
for(int i =0; i < N-1; i++) {
if(arr[i+1] - arr[i] > result ) result = arr[i+1] - arr[i];
}
// for(int i =0 ; i< N ; i++) {
// printf("%lld ", arr[i]);
// }
// printf("\n");
return result;
} else {
long long min = 0;
long long max = 1e18;
long long low;
long long high;
MinMax(min, max, &low, &high);
min = low;
max = high;
long long distance = (high - low + N - 2) / (N - 1);
long long result = 0;
long long cmp = low;
long long left = min+1;
long long right = left + distance;
while(1) {
if(left >= max) break;
if(right >= max) right = max - 1;
MinMax(left, right, &low, &high);
// printf("left %d, right %d, low %lld, high %lld\n", left, right, low, high);
left = right + 1;
right = left + distance;
if(low == -1) continue;
if(result < low - cmp) result = low - cmp;
cmp = high;
}
if(max - cmp > result) result = max - cmp;
return result;
}
return 0;
}
