只要暴力即可。

而且题目里明确写着

“UPD：本题测试数据随机，可能是假题。”

所以按照概率算一下，大概就是 $O(n)$ 多一点?

但是不知道要多多少，所以来问一下