想到了严格 $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看看吧

还是线段树好写得多。。

什么是单调堆栈= =不就是优先队列么wwwwwwwwwww

P.1212去楼下的，假不假

终于AC了。。用的线段树+DFS，最最最笨的方法。。膜拜各位神犇大牛的贪心、单调栈。。本蒟蒻啥也不会

dfs寫脲了。。80分。。一會兒打個線段樹

怎么AC的呢？先写了个贪心。这个贪心存在一个bug，就是对于类似于第九组那样的数据会超时,数据太极限了。。当然，bug不只是那组数据，而是对于一类数据--波动幅度大的数解小，波动幅度小的数解大eg.1 5 2 3 4,我的贪心就会退化为O（n^2），所以用了极具针对性的方法处理了这个问题。。开个数组，把身高从大到小排序，然后用一个指针，指向当前剩下的没有被计算的数据的最大值。。找出一个解后，如果出现右边的奶牛身高是这个值，就直接从这个值之后开始寻找解。。思路说的不怎么清晰，也不值得借鉴、。、依然有反例

贪心90的路过。。。很简单很简答的贪心。。。

单调堆栈撸过

法一：单调栈预处理然后枚举，针对n很大但单调长度很短的数据增加优化（可行的最大长度（即枚举时只枚举到该点之后的最大数，如果还有坑数据，再预处理该段长度，然后枚举时判断是否需要枚举（如果最长长度都小于ans还枚举干嘛）））
法二 ：先用st或线段树求出区间最大和最小,然后深搜或者广搜都行,推荐深搜,好写.每次搜加两个关键字,分别为区间的左端点l和右端点r,然后用区间最大最小求出他们之间的最大值和最小值的下标ml,mr.如果mr>ml说明区间合法,维护ans,如果ml>=mr说明区间不合法,需要交换.最后就是将区间裂成(l,ml)(ml+1,mr-1)(mr,r),继续搜.
法三：我知道一定有正解，本人太弱想不出。。。