Official Analysis (C++)

Solution ($O(N\sqrt N)$)

See Eric Zhang's comment.

Alternate (Fake) Solution

First write some $\mathcal{O}(N^2)$ DP that is somehow fast enough to pass test cases 1-6.

This won't work for test cases 7-11, but these test cases are quite special!