We solve this task with dynamic programming. Let ~\text{dp}[X]~ mark the minimal mistake of constructing a histogram with given points such that the rightmost point of the histogram is on the ~x~-coordinate ~X~. Now we could conceptually solve this problem by trying to connect each point on the coordinate ~X~ with the points left to it on the same height (~y~-coordinate), which would lead us to the correct solution of complexity ~\mathcal O(N^3)~, which is too slow.

This complexity implicitly assumes that the problem of determining the function ~\text{abserror}~ or ~\text{diffcount}~ between two points is solved in complexity of ~\mathcal O(N)~.

In order to speed up the given algorithm, let's notice that when calculating ~\text{dp}[X]~ it is enough to observe only the previous ~x~ coordinate of a certain point (because the histogram can arbitrarily change the height without any additional errors).

This observation, along with a careful implementation, leads us to complexity ~\mathcal O(N^2)~ which was enough for ~50\%~ of points.

To further speed up the algorithm, it is necessary to calculate ~\text{diffcount}~ and ~\text{abserror}~ between two points in complexity ~\mathcal O(1)~ instead of ~\mathcal O(N)~. Let's show that this is possible for ~\text{abserror}~ (the more difficult case), whereas we'll leave ~\text{diffcount}~ for you to practice.

Let's notice that ~\text{abserror}~ between two points on the same ~y~ coordinates ~a~ and ~b~ is equal to ~\text{abserror}(a, b) = \text{abserror}(0, b) - \text{abserror}(0, a)~, where ~0~ marks a point (sometimes fictional) on ~x~-coordinate ~0~ with equal height as ~a~ and ~b~. In other words, it is necessary for each point ~p~ to determine only ~\text{abserror}(0, p)~.

This problem can be solved for all points in complexity ~\mathcal O(N \log N)~ by using Fenwick tree (logarithmic structure) or segment (tournament) tree and scanline algorithm in the direction of the increasing ~x~-coordinate.

Complexity: ~\mathcal O(N \log N)~