以下では説明の簡略化のため \(A_x, A_{x+1}, \ldots, A_{y-1}\) のことを区間 \([x,y)\) と呼びます。

\(l < m < r\) のとき区間 \([l,r)\) における \(2\) 番目に大きな値は区間 \([l, m)\) における最大値、区間 \([l, m)\) における \(2\) 番目に大きい値、区間 \([m, r)\) における最大値、区間 \([m, r)\) における \(2\) 番目に大きい値のいずれかになります。

また同様に、区間 \([l,r)\) における最大値は区間 \([l,m)\) における最大値あるいは区間 \([m,r)\) における最大値のいずれかとなります。

したがって (最大値, 最大値の個数, \(2\) 番目に大きい値, \(2\) 番目に大きい値の個数) の組は区間 \([l,m)\) および区間 \([m,r)\) についてわかっていれば区間 \([l,r)\) についても定数時間で計算可能であるため segtree を用いて全体として時間計算量 \(O(N + Q\log N)\) でこの問題が解けます。