#include<iostream>
#include "gap.h"
#define l 1000000000000000000
using namespace std;
long long subt1(long long n)
{
long long tf,ts,pf,ps,mr=0;
MinMax(0,l,&tf,&ts);
for(int i=2;i<=n/2;i++)
{
pf=tf;ps=ts;
MinMax(pf+1,ps-1,&tf,&ts);
if(tf-pf>mr) mr=tf-pf;
if(ps-ts>mr) mr=ps-ts;
}
if(n%2)
{
if(tf+1<=ts-1)
MinMax(tf+1,ts-1,&pf,&ps);
if(pf-tf>mr) mr=pf-tf;
if(ts-pf>mr) mr=ts-pf;
}
else if(ts-tf>mr) mr=ts-tf;
return mr;
}
long long subt2(long long n)
{
long long tl,tr,mi,ma,pma=0,mr=0;
MinMax(0,l,&tl,&tr);
tl++;tr--;
long long in=(tr-tl+1)/(n+1);
for(int i=1;i<n;i++)
{
MinMax(tl,tr,&mi,&ma);
tl+=in;tr+=in;
if(mr<mi-pma)
mr=mi-pma;
if(ma!=-1) pma=ma;
}
return mr;
}
long long findGap(int T, int N)
{
if(T==1)
return subt1(N);
return subt2(N);
}
