各 \(i\) について, \(A_j \gt A_j\) となる \(j (j \lt i)\) のうち最大のものを \(B_i\) とする. この \(B_i\) は \((A_i, i)\) を \(A_i\) で降順にソートして \(i\) を赤黒木に順に入れていくこので求められる.

このとき, 区間 \([l, r]\) の “高い” 個数は \(B_i\) のこの区間の \(l\) 未満の個数となる. \(B_i\) を昇順にソートし, クエリも先読みして \(l\) の昇順にソートしてクエリ実行の際に \(B_i < l\) となる \(B_i\) を個数を管理する Fenwick Tree に入れていく.