#include <iostream>
#include <set>
#include "gap.h"
#define INF 1000000000000000000
using namespace std;
set <long long> s;
long long findGap(int T, int N)
{
if (T == 1)
{
long long minimum, maximum;
MinMax(1, INF, &minimum, &maximum);
s.insert(minimum);
s.insert(maximum);
for (int i = 1; i < (N + 1) >> 1; i++)
{
long long val1, val2;
MinMax(minimum + 1, maximum - 1, &val1, &val2);
s.insert(val1);
s.insert(val2);
minimum = val1;
maximum = val2;
}
long long maxGap = 0, last = minimum;
for (auto it : s)
{
maxGap = max(maxGap, it - last);
last = it;
}
return maxGap;
}
else
{
long long minimum, maximum;
MinMax(1, INF, &minimum, &maximum);
long long gapLength;
if ((maximum - minimum) % (N - 1) == 0)
gapLength = (maximum - minimum) / (N - 1);
else
gapLength = (maximum - minimum) / (N - 1) + 1;
for (long long i = minimum + 1; i <= maximum - 1; i = i + gapLength)
{
long long val1, val2;
MinMax(i, i + gapLength - 1, &val1, &val2);
s.insert(val1);
s.insert(val2);
}
s.erase(-1);
long long maxGap = 0, last = minimum;
for (auto it : s)
{
maxGap = max(maxGap, it - last);
last = it;
}
return maxGap;
}
}
