#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll isbet(ll a, ll b)
{
ll c = (ll)sqrt(b - a + 2);
vector<ll> vec;
for (ll i = 1; i <= c; i++)
{
vec.push_back(i);
}
for (ll i = max(a, c) + c; i <= b; i += c)
{
vec.push_back(i);
}
vec.push_back(b+1);
return collisions(vec);
}
int hack()
{
ll mx = 1e6;
ll mn = 1;
while (mx > mn + 7)
{
ll c = (mx + mn) / 2 - mn;
ll d = (ll)sqrt(c);
if (c - d * d - 2 < d * d + 2 * d - c - 1)
c = d * d - 2;
else
c = d * d + 2 * d - 1;
if (mn != 1)
c++;
if (isbet(mn, mn + c))
{
mx = mn + c;
}
else
{
mn = mn + c + 1;
}
}
for (ll i = mn; i < mx; i+=2)
if (collisions({1, 1 + i * (i + 1)}))
{
if (collisions({1, 1 + i}))
return i;
return i + 1;
}
return mx;
}
