ABC189 C Mandarin Orange
$ xを全探索することを考える. すると, $ xが決まれば$ (l, r)は貪欲に決まる. 具体的には$ lは$ x \leq A_i((今見ているindex) \leq i \leq (値がxとなる最小のindex))となるような最小の$ iとすればよい($ rも同様にして定まる).
よってあとは各値について登場するindexを2次元配列に保存しておき, setを用いて二分探索をすることで求められる. setに番兵として最初に-1, Nを挿入しておくと実装が楽である. 計算量は$ O(N \log N)となる.
ほかにも解法はたくさんある(例えば$ O(N^2)の簡単な解でも間に合うし, ヒストグラム内の最大長方形問題として$ O(N)で解くこともできる).