哲学家的沉思

做法1

考虑离线处理，将所有询问挂到区间左端点上。

逆序跑单调栈(递减)，假设现在栈顶元素为 $l$ 。此时，对于询问 $l, r$ ，答案为单调栈内值属于 $[l, r]$ 的元素个数。

由于栈顶为 $l$ ，答案为单调栈的某一个后缀。通过二分后缀的起点，就可以以 $O(\log n)$ 的时间复杂度求解。

单调栈部分共 $O(n)$ ，每一个询问 $O(\log n)$ ，总的时间复杂度为 $O(q\log n)$ 。

（以下为口胡

通过单调栈还可以找出对于每一个 $i$ ，他后面第一个大于它的元素 $nxt_i$ 。然后问题就可以转化为从 $i$ 可以跳到 $nxt_i$ ，问从 $l$ 开始跳，最少几步可以跳到 $r$ 或 $r$ 之后。

现在就是弹飞绵羊，究极经典的题目了，分块或者LCT搞一搞？