#include "hack.h"
#include <vector>
// 辅助函数：计算当桶数为 mid 时，1~K 个数会产生多少次碰撞
long long calculate_collisions(long long K, long long n_val) {
if (n_val >= K) return 0;
long long q = K / n_val;
long long r = K % n_val;
// 有 r 个桶装了 q+1 个数，每个桶碰撞 (q+1)*q/2 次
// 有 (n_val - r) 个桶装了 q 个数，每个桶碰撞 q*(q-1)/2 次
long long res = r * (q * (q + 1) / 2) + (n_val - r) * (q * (q - 1) / 2);
return res;
}
int hack() {
// 1. 我们直接发一个长度为 1,000,000 的大招
long long K = 1000000;
std::vector<long long> x;
for (int i = 1; i <= K; ++i) x.push_back(i);
long long actual_c = collisions(x); // 消耗 1,000,000 额度
// 2. 如果没有碰撞，说明 n 比 K 还大 (n > 1,000,000)
if (actual_c == 0) {
// 这部分属于 Subtask 3，需要更高级的策略，
// 现在我们可以随便返回一个大数，或者尝试其他逻辑。
return 1000001;
}
// 3. 如果有碰撞，n 一定在 [2, 1,000,000] 之间
// 我们用二分查找来锁定 n
long long low = 2, high = K;
long long ans = 2;
while (low <= high) {
long long mid = low + (high - low) / 2;
if (calculate_collisions(K, mid) >= actual_c) {
ans = mid; // 碰撞够多，说明 n 可能还能再大点
low = mid + 1;
} else {
high = mid - 1; // 碰撞太少，说明 n 猜大了
}
}
return (int)ans;
}
