首先，很典的，对于一个区间\([l,r]\)，他的最少操作次数为：
\[r - l + 1 - \sum_{i=l}^{r-1}{[\max_{j=l}^{i}{a_j}<\min_{j=i+1}^{r}{a_j}]}
\]
正难则反，我们考虑先算出\(\sum_{l=1}^{n-1}{ \sum_{r=l+1}^{n}{(r-l+1)} }\)，再拿后面那一部分减去前面那一部分
然后就到了经典的交换求和顺序的环节
我们枚举\(\max_{j=l}^{i}{a_j}\)的最大值对应的位置，记作\(b\)，在\(b\)左边找到距离最近的\(a\)满足\(a_a>a_b\)(这里\(a_i\)数组和\(a\)变量注意区分)，在\(b\)右边找到距离最近的\(c\)满足\(a_c > a_b\)，在\(c\)右边找到距离最近的\(d\)满足\(a_d < a_b\)，则左端点的范围为\((a,b]\)，右端点的范围为\([c,d)\)，最终答案为\((b-a) \times (d-c)\)
我们考虑怎么找到\(a,c,d\)。我们可以把他们排序后从小到大删数，把\(<b\)的和\(>b\)的放到两个\(set\)里，每次二分即可，这么做是\(O(n \log{n})\)的
不过还有\(O(n)\)的做法，我们发现\(a,c\)的单调栈都很好维护，最不好维护的是\(d\)的单调栈，因为我们要保证他在\(c\)的右边。然后这里就要用到一个小技巧：单调栈套单调栈
听起来好像很吓人，那其实只是在维护\(c\)的时候，如果\(c\)栈里的元素被弹了出来，我们再把弹出来的元素放到\(d\)栈中去，这样就可以保证\(d\)栈的元素一定在\(c\)栈之后啦(理论可行)
这样最终复杂度\(O(n)\)