题目中有关键的一句话：

It is guaranteed that the sum of $n$ over all test cases is no more than $10^6$ .

表明了所有 $n$ 的和不超过 $10^6$ ，因此只需要用大概 $O(n)$ （虽然我也没有仔细算）的时间复杂度即可

不过翻译中并没有翻译这句话，做题时一直在怀疑人生，输入就要 $O(n)$ ， $3s$ 跑 $10^5\times10^6$ 完全不够

题目翻译言简意赅是可以，也是提倡的，但也不能因为言简意赅而省略掉重要内容