考虑维护出每一个点左边第一个比它大的位置，右边同理，这样有一个合法区间。

然后对询问离线，由于要求只包含区间内的贡献，扫描线+线段树解决。

T1

考虑一下笛卡尔树，然后分析出答案等于这个区间形成的笛卡尔树的所有节点的子树和。

再做一步转化就等价于有多少个节点存在祖先与后代的关系。

这个又等价于最开始的那个问题。

T2

题意转化出来是：

一个端点为最大值，另一个端点是次大值贡献为p1。

一个端点为最大值，另一个端点不是次大值贡献为p2。

考虑先把所有有一个端点为最大值得区间全部记贡献为p2。

然后由于条件1和条件2的第二部分是互补的,只需要修改一部分贡献为p1即可。（如果不是互补的,你只改一部分另一部分还会包含不合法的。）

如果考虑去找以x为最大值,哪些位置可以为次大值并不容易。

考虑反向操作,找以x为次大值，哪些位置可以为最大值。

这个显然就只有两个位置。（也就是之前预处理出来的左/右第一个比它大的位置）

同样的方法用线段树维护即可。