想定解法は segment tree だが、O(N^2) の DP を、隣の状態より strict に良い状態だけを残すような枝刈りしても通る。発見した中でのワーストケースでは、 与えられる点が、 200000, 1, 100000, 50000, 75000, ... のときに、保持する必要がある状態数が 20…