#include <bits/stdc++.h>
using namespace std;
long long collisions(vector<long long> x);
int hack() {
// 1. Check small n (= 100000)
vector<long long> q;
for (int i = 1; i <= 100000; ++i) q.push_back(i);
if (collisions(q) > 0) {
for (int d = 2; d <= 100000; ++d) {
if (collisions({0LL, (long long)d, 2LL * d}) == 3) {
return d;
}
}
}
// 2. n > 100000 – use a random set to estimate n
mt19937 rng(12345); // fixed seed for reproducibility
set<long long> used;
vector<long long> randQ;
while ((int)randQ.size() < 100000) {
long long x = uniform_int_distribution<long long>(1, 1000000000)(rng);
if (used.insert(x).second) randQ.push_back(x);
}
long long c = collisions(randQ);
long long pairs = (long long)100000 * 99999 / 2;
long long est = pairs / max(1LL, c);
// Search a window around the estimate
long long low = max(2LL, est / 2);
long long high = min(1000000000LL, est * 2);
for (long long d = low; d <= high; ++d) {
if (collisions({0LL, d, 2LL * d}) == 3) {
return d;
}
}
// Fallback (should rarely be reached)
for (long long d = 2; d <= 1000000000; ++d) {
if (collisions({0LL, d, 2LL * d}) == 3) return d;
}
return -1;
}
