这道题难度一看还以为要用单调队列+DP之类的东西，结果 $n \le 3000$。

这不是直接 $O(n^2)$ 模拟吗？根本就不需要前缀和优化呀？题解都把这道题复杂化了吧。