yukicoder No.905 Sorted?(★2)

問題：No.905 Sorted? - yukicoder

解答：#475788 (C++14) No.905 Sorted? - yukicoder

解法：各iごとに広義単調増加、広義単調減少となる上限のインデックスを求める。

求め方は、広義単調増加/減少の間でiをストックし、増加/減少でなくなった時にストックされた各インデックスについて上限を更新するイメージ。

解説は累積和を使っている。