解法

イメージはしゃくとり法(とスライド最小値)です。

$[l, r]$ が条件を満たすなら、 $[l + 1, r]$ が条件を満たすのはいいでしょう(もちろん $l + 1 \leq r$ です)

そして $[l, r + 1]$ が条件を満たすなら、 $[l, r]$ も条件を満たします。

そうすると、しゃくとり法で $l$ をすすめながら $r$ を進めていきましょう。最大値の管理はスライド最小値のような感じでdequeや知ってる人ならSWAGを用いるといいです。

よってこの問題を $O(n)$ で解くことができました。

提出コード