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