空で初期化されたリスト \(L\) を用意し， \(i=1,2,\dots,N\) について以下を行えばよいです．

• \(L\) に \(A_i\) を追加する．
• \(i\ge 3\) のとき， \(L\) を降順に並べたとき \(3\) 番目に来る要素を出力する．

これは \(L\) を multiset で管理し，以下のように実装すればよいです．

• 追加: L.insert(A[i])
• 取得: *prev(L.end(), 3)

計算量は \(O(\log N)\) です．