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