#include "hack.h"
#include <vector>
#include <math.h>
#include <iostream>
using namespace std;
int hack(){
vector<long long> x;
// x={1,48,49,50};
// long long a=collisions(x);
// std::cout<<a<<' ';
long long l=2,r=1000000000;
while(l<r){
x.clear();
long long mid=(l+r)/2;
long long k=sqrt(mid-l+1);
if(k==0){
x.emplace_back(1);
x.emplace_back(mid+1);
long long a=collisions(x);
if(a)return mid;
return r;
}
for(int i=1;i<=k;i++)x.emplace_back(i);
int now=min(l+k,mid);
while(now<=mid){
x.emplace_back(now);
now+=k;
// cout<<now<<' ';
}
x.emplace_back(mid+1);
long long a=collisions(x);
// std::cout<<l<<' '<<r<<' '<<a<<'\n';
if(a){
if(l==2)r=min((r*r/a/a),(long long)mid);
else r=mid;
}
else l=mid+1;
// std::cout<<'\n';
// std::cout<<l<<' '<<r<<'\n';
// for(auto v:x)std::cout<<v<<' ';
// std::cout<<'\n';
}
return r;
// return -1;
}
