#ifndef KHOA
#include "gap.h"
#endif // KHOA
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(int i = 0, _r = (r); i < _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define size(v) ((ll)(v).size())
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
const ll MOD = 1e9 + 7, N = 2e5 + 10, INF = 2e18, LOG = 21;
ll a[N];
#ifdef KHOA
ll A[N] = {-2008, };
void MinMax(ll x,ll y,ll *z,ll *t){
bool ok = 0;
FOR(i,1,10){
if(x <= a[i] && !ok){
*z = a[i];
ok = 1;
}
if(a[i] <= y)*t = a[i];
}
}
#endif
ll findGap(int T, int n){
ll mi,mx,v1,v2;
MinMax(0,1e18,&mi,&mx);
if(n==2)
return mx-mi;
// [mi+1,mx-1]
// mx-mi-1
ll len=(mx-mi+n-1)/(n-1);
ll last=mi,ans=0;;
for(ll cmi=mi+1,cmx=mi+len,i=1;i<n;i++,cmi+=len,cmx+=len)
{
if(cmx>=mx)cmx=mx-1;
if(cmi<=cmx)
{
MinMax(cmi,cmx,&v1,&v2);
if(v1!=-1)
{
ans=max(ans,v1-last);
last=v2;
}
}
else{
break;
}
}
ans=max(ans,mx-last);
return ans;
}
#ifdef KHOA
int main(){
FOR(i,1,10)a[i] = i * 10,cerr<<a[i]<<' ';
cerr<<endl;
cout<<findGap(1, 10);
}
#endif
