#include "gap.h" #include<bits/stdc++.h> using namespace std; long long findGap(int t,int n){ // Subtask 2 long long ans; if(t==1){ long long a[n],l=0,r=1e18; for(int i=0;i<(n+1)/2;++i){ MinMax(l,r,&a[i],&a[n-i-1]); l=a[i]+1,r=a[n-i-1]-1; } ans=0; for(int i=0;i<n-1;++i) ans=max(ans,a[i+1]-a[i]); }else{ long long s,e; MinMax(0,(long long)1e18,&s,&e); vector<long long> v; v.emplace_back(s); ans=(long long)(e-s+n-2)/(n-1); for(long long l=s+1;l<e;l+=ans+1){ long long a,b; MinMax(l,l+ans,&a,&b); if(a==-1) continue; v.emplace_back(a); if(a!=b) v.emplace_back(b); } v.emplace_back(e); for(int i=1;i<(int)v.size();++i) ans=max(ans,v[i]-v[i-1]); } return ans; }