#include "hack.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int hack()
{
vector<long long> q = {1};
for (long long diff = 2; diff * (diff + 1) / 2 <= 1e5; diff++)
{
q.push_back(diff * (diff + 1) / 2);
}
long long l = 1;
long long r = q.size();
int ans;
while (l < r)
{
long long mid = (l + r) / 2;
vector<long long> query = vector(q.begin(), q.begin() + mid);
long long response = collisions(query);
if (response >= 1)
{
r = mid;
ans = mid;
}
else
l = mid + 1;
}
return q[ans] - q[ans - 1];
}
