#include <bits/stdc++.h>
using namespace std;
long long collisions(std::vector<long long> x);
using ll = long long;
int hack() {
ll m = 31623;
ll l, h;
vector<long long> vec;
for (ll i = 0; i < m; i++) vec.push_back(i + 1);
if (collisions(vec)) {
l = 1, h = m;
while (l < h) {
ll mid = (l + h) / 2;
vec.clear();
for (ll i = 0; i < mid; i++) vec.push_back(i + 1);
if (collisions(vec)) {
h = mid;
} else {
l = mid + 1;
}
}
return l - 1;
}
l = 1, h = m;
while (l < h) {
ll mid = (l + h) / 2;
vec.clear();
for (ll i = 0; i < m; i++) vec.push_back(i + 1);
for (long long i = l; i <= mid; i++) {
vec.push_back(i * m + 1);
}
if (collisions(vec)) {
h = mid;
} else {
l = mid + 1;
}
}
ll q = l;
l = 0, h = m - 1;
while (l < h) {
ll mid = (l + h) / 2;
vec.clear();
vec.push_back(q * m + 1);
for (ll i = l; i <= mid; i++) {
vec.push_back(i + 1);
}
if (collisions(vec)) {
h = mid;
} else {
l = mid + 1;
}
}
return q * m - l;
}
