#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
#define SZ(v) ((int)(v).size())
using ll = long long;
void MinMax(ll lo, ll up, ll *mn, ll *mx);
ll findGap(int sous_tache, int nb_elem)
{
if (sous_tache == 2)
{
ll smallest, biggest;
MinMax((ll)0, (ll)1e18, &smallest, &biggest);
ll delta = ceil( (long double)(biggest - smallest) / (nb_elem - 1));
vector<ll> sparse_elem;
for (ll k(0); k < nb_elem - 1; ++k)
{
ll l, r;
MinMax(smallest + k * delta, smallest + (k+1) * delta-1, &l, &r);
if (l != -1)
{
sparse_elem.push_back(l);
sparse_elem.push_back(r);
}
}
sparse_elem.push_back(biggest);
ll ans = delta;
for (int i(0); i + 1 < SZ(sparse_elem); ++i)
ans = max(ans, sparse_elem[i+1] - sparse_elem[i]);
return ans;
}
else
{
ll arr[nb_elem];
MinMax(0LL, (ll)1e18, arr, arr + nb_elem - 1);
for (int i(1), j(nb_elem - 2); i <= j; i++, j--)
MinMax(arr[i-1]+1, arr[j+1] - 1, arr + i, arr + j);
ll ans(0);
for (int i(0); i < nb_elem-1; ++i)
ans = max(ans, arr[i+1] - arr[i]);
return ans;
}
}
