rt，很明显有 $O(n^2\log^2n)$ 的做法，可以加一个 $n\le1000$ 的加强版