\(T_i=(\) ビル \(i\) が見えなくなるビル \(j(1\leq j\leq i)\) としてありうる最大値 \((\) 存在しない場合は \(-\mathrm{inf}\) \())\) とします。

\(T\) は \(j\) の降順にビル \(j\) から見えるビルをstackなどで求める過程で \(O(N)\) で求まります。

各クエリ \(l_i,r_i\) について、答えは \((T_{r_i+1},T_{r_i+2},\dots,T_N)\) に含まれる \(l_i\) 未満の値の個数となり、これは MergeSortTree によって \(O(\log^2N)\) で求めることができます。

計算量は \(O(N\log N+Q\log^2 N)\) です。実装例(C++ 349ms)