>>196 C++ O(N log N)
セグメント木を使うと区間 max の二分探索を O(log N) で行える
atcoder の aclib を使用
https://wandbox.org/permlink/8rm8MsauDMJhvpAf