题意还请自行阅读。
思路
如果直接模拟，每次插入都需要线性探测，当插入位置是连续时，时间复杂度将会退化至 O(q2)O(q^2)O(q2)，难以接受，考虑其它方法实现或优化。
注意到数组长度为 220≈1e62^20 \approx 1e6220≈1e6，但操作次数 q≤2×1e5q \le2 \times 1e5q≤2×1e5，因此最大插入 qqq 个元素，数组有大量空位。
我们可以利用类似并查集的思想来加速找空位的过程。
* 维护一个数组 next，next[i] 表示从位置 iii 开始，下一个可能为空位的位置（包括自身）。初始时 next[i] = i。
* 当需要插入时，我们通过 Find(x % n) 找到当前应该插入的空位 ppp，然后：
1. 将 apa_pap 设为 xxx。
2. 将 next[p] 指向下一个可能的空位位置，即 next[(p+1) % n]，表示这个位置已经被占用。
* Find 函数采用路径压缩，使得后续查找更快，均摊复杂度接近 O(1)O(1)O(1)。
查询操作直接输出 ax mod na_{x \bmod n}axmodn 即可，无需任何额外处理。
