#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
bool dntm (int l, int a, int b)
{
vector <long long> v_ask;
for (int i = 1; i <= a; i ++) v_ask.push_back (i);
for (int i = a + l; i <= a * b + l; i += a) v_ask.push_back (i);
return collisions (v_ask);
}
bool check_inside (int l, int r)
{
int dif = r - l;
int d = sqrt (dif + 1);
if (d * (d + 1) > dif + 1)
{
if (dntm (l, d, d)) return true;
dif -= d * d;
}
else
{
if (dntm (l, d, d + 1)) return true;
dif -= d * (d + 1);
}
if (dif < 0) return false;
d = sqrt (dif) + 1;
return dntm (r - d * d + 1, d, d);
}
int hack()
{
int le = 5e8, ri = 1e9;
while (le < ri)
{
int mid = (le + ri) / 2;
if (check_inside (le, mid)) ri = mid;
else le = mid + 1;
}
vector <int> divs;
for (int i = 2; i * i < le; i ++)
{
if (le % i == 0)
{
divs.push_back (i);
divs.push_back (le / i);
}
}
sort (divs.begin (), divs.end ());
divs.push_back (le);
int l = 0, r = divs.size () - 1;
while (l < r)
{
int mid = (l + r) / 2;
vector <long long> v_ask = {1};
for (int i = l; i <= mid; i ++) v_ask.push_back (divs[i] + 1);
//for (auto i: v_ask) cout << i << ' ';
//cout << '\n';
if (collisions (v_ask)) r = mid;
else l = mid + 1;
}
return divs[l];
}
