#include "hack.h"
#include <vector>
using namespace std;
const int N = 1000000000;
typedef vector<long long> vl;
bool check(int l, int r) {
int m = 1;
while (m * m < r - l)
m++;
int q = (r - l + m - 1) / m;
vl aa(m + q);
for (int i = 0; i < m; i++)
aa[i] = i + 1;
for (int i = 0; i < q; i++)
aa[m + i] = min(m * (i + 1) + l, r);
return collisions(aa) != 0;
}
int hack() {
int lower = 1, upper = N + 1;
while (upper - lower > 1) {
int n = (lower + upper) / 2;
if (check(lower, n))
upper = n;
else
lower = n;
}
return lower;
}
