本题的最优解是 $\mathcal O(n)$，我知道这一点，而且 官方题解 也是这一解法。

本题原来的数据范围是 $2\times 10^6$，值域 $10^9$ 并输出方案，但是考虑到作为 div2 B 有通过率要求，弱化成了现在的 $5\times 10^3$ 且不要求构造，故意放了 $\mathcal O(n^2)$ 解法通过。

由于上述原因，不接受一切以 $\mathcal O(n^2)$ 做法能够通过为理由的加强数据申请，也不接受一切以 $\mathcal O(n^2)$ 做法被卡常无法通过为理由的开大时限申请。

如果存在一些假做法通过，可以联系我加强数据。

尽管我们已经做了很多的弱化处理，最终通过率仍然没有达到要求。团队成员解题过程均比较顺利，没能意识到本题可能存在的个人差问题，我（作为出题人）代表团队成员谢罪。我们也愿意接受扣工资的处罚。