首先，如果你写过P9058的话，应该会想到支配点对这个 trick,我们不妨将此题的套路搬到这套题上.
定义点对 \((i,j),a_i\le a_j\)，当 \((i,j)\) 被支配当且仅当存在 \(i<k<j\) 满足 \(a_i\le a_k \le a_j\)。
相应的，一个有效的点对 \((i,j)\)，其中 \(i\) 满足 \(i\) 最大且 \(a_i<a_j\)。
我们不妨证明这个结论：
反证法，有 \(a_{pre},a_i \le a_j\)，其中 \(pre<i<j\) ，假设 \((pre,j)\) 为有效点对，
点对 \((pre,i)\) 的权值为 \(|a_i-a_{pre}|\)，\((pre,j)\) 的权值为 \(a_j-a_{pre}\)。
在之前的证明中，需要满足 \((pre,i)\) 的权值 小于 \((pre,j)\) 的权值才能得证，但是这里却失效了，怎么办呢？？？
不妨沿着此思路，固定右端点 \(j\)，挖掘在区间 \([1,i)\) 这个区间内更优秀的左端点 \(pre\) 所满足的性质。
如果 \(pre\) 这个左端点在区间 \([1,i)\) 中更加优秀，有：\(a_i<a_{pre}<a_j\) 且 \(a_{pre}-a_i>a_j-a_{pre}\)，继续考虑在区间 \([1,pre)\) 区间内更加优秀的左端点 \(pre'\)，有：\(a_{i}<a_{pre'}<a_{pre}\) 且 \(a_{pre'}-a_{pre}>a_j-a_{pre'}\)。
不妨简化下式子，得：\(2a_{pre}>a_i+a_j\)，\(2a_{pre'}>a_{j}+a_{pre}\)，发现左端点的权值是以指数级别增加的，那么对于一个右端点最多有 \(log_2V\) 个左端点。
如何实现?