本来这种写法应该是维护上凸壳的： while (l < r && Y(q[r - 1], q[r]) * X(q[r], i) <= Y(q[r], i) * X(q[r - 1], q[r])) r--;

但是此题中，如果 $dp$ 值递增，将会不可避免的导致斜率递减，最优决策点递减，以及 $x$ 坐标递减，所以我们要维护一个反方向的下凸壳，也就是上面维护上凸壳的写法。

本质还是下凸壳，只是坐标轴反了，所以变成了正常坐标下的上凸壳。