想到了严格 $O(n\log(n))$ 的解法:
首先我们用单调栈或者 $\text{std::set}$ 预处理出每个值 $a_l$ 右边第一个不大于它的值 $a_r$ 的位置, 这样的话区间 $(l,r)$ 就是以 $l$ 为左端点的合法区间的右端点的可能位置.
然后我们根据 $r$ 的大小升序排序, 同时使用一个树状数组维护 $a_i$ 后大于前面所有点的点值 $a_r$ 与位置 $r$ (若点值相等取下标更小的), 将点逐个加入树状数组, 在加入到某个 $(l,r)$ 的 $r-1$ 的位置的时候就可以查询 $l$ 得到最大的右端点.
总时间复杂度中, 预处理是 $O(n)$ 或者 $O(n\log(n))$ 的, 最后树状数组中每个点都至少要插入/查询一次, 树状数组部分总时间复杂度 $O(n\log(n))$, 整个程序时间复杂度为 $O(n\log(n))$.
最后注意特判 $ans=0$ 的情况就行了
可以参考标程理解一下

奇迹暴力

答案可能是0，2，但不会是1!
请务必特判...

题解里面根据解法三写的标程写出来了QwQ ， 题解看不懂的戳这里

答案可能是0，2，但不会是1 ans是1要特判·-·

回复 @KEVI_ :
6
1 9 2 3 4 5

我的代码只有70分，但是不知道哪里错了。
这是我的思路：
先从左往右标记最低点（红色），然后枚举找最高点（绿色），当枚举到最高点（绿色）时候更新与最近最低点（红色）的距离。

我举了很多例子，但是似乎都是正确的，奇怪。

在本地测会Runtime Error，提交就不会= =
本地递归次数太多好像爆栈了。。
蒟蒻不会单调队列。。就写个dfs看看吧