この問題は，セグメント木に複数の値の組を載せることによって解きます． ACL/segtree をベースに実装方法の説明を行いますので，以降を読む前にあらかじめ確認しておくことを推奨します．

ACL のセグメント木は，載せる値の組の構造体 \(S\)，区間結合時の二項演算 \(op\)，および単位元の値 \(e\) を指定して利用します．ここでの目標は，1 点の変更および区間の値の取得に対応できるように，\(S, op, e\) を設定することです．

今回の問題では，「区間の二番目の最大値の個数」を取得することが要求されます．この要件を満たせるように， \(S, op, e\) を設定していきましょう．

唐突ですが，\(S\) に（区間の最大値，区間の最大値の個数，区間の二番目の最大値，区間の二番目の最大値の個数）を指定することにします．これは，区間結合時の二項演算を実現するのに必要な情報となるから，というのが理由になります（詳細な演算の方法は後述）．以降，これら \(4\) 個の値をそれぞれ \((f, cf, s, cs)\) とおきます．

\(op\) を具体的に考えましょう．ここですべきことは，左側の区間についての情報 \(S_l\) および右側の区間についての情報 \(S_r\) が与えられた際に，それを結合した区間についての情報 \(S_c = (f_c, cf_c, s_c, cs_c)\) を求める，ということになります．以降，\(S_l = (f_l, cf_l, s_l, cs_l)\) および \(S_r = (f_r, cf_r, s_r, cs_r)\) とします．

具体的な \(S_r = (f_r, cf_r, s_r, cs_r)\) の求め方についてですが

• \(f_c\) について．\(f_c = \max(f_l, f_r)\) となります．
• \(cf_c\) について．\(f_l\) と \(f_r\) の中で，\(f_c\) と等しい値に対応する個数の和となります．
• \(s_c\) について．\(f_l, f_r, s_l, s_r\) の中で，二番目に大きい値となります．具体的な形は実装例を参照してください．
• \(cs_c\) について．\(f_l, f_r, s_l, s_r\) の中で，\(s_c\) と等しい値に対応する個数の和となります．

よって，\(op\) には \(S_l\) および \(S_r\) が与えられたときに，上の演算によって求めた \(S_c = (f_c, cf_c, s_c, cs_c)\) を返す関数を指定すればよいことになります．

\(e\) についてですが，結合時に影響のない値，すなわち

• \(S_e = (f_e, cf_e, s_e, cs_e) \) に対し，\(S\) と \(S_e\) を結合させたときに \(S\) を返すような \(S_e\)

を適切に設定すればよいです．今回の制約では，\(S_e = (-1, 0, -2, 0)\) などに設定すればよいでしょう．

実際に使用する際には，\(S\) の初期化（セグ木の各点に乗せる情報）も考える必要があります．このときは \(1\) 点だけの場合に，\(S\) の各値がどうなるか考えればよいです．まず，明らかに \(f = A_i, cf = 1\) なので，それを指定すればよいです．\(s, cs\) については，今回の場合は存在しないですが，仮想的に結合時に影響のない適当な値（\(s = -1, cs = 0\) など）に設定すればよいでしょう．結局，各要素の初期化の際には，seg.set(i, S{A[i], 1, -1, 0}) などのように記述すればよいです．（一点更新の際も，ほぼ同様のことをすればよいです）

これらを用いることで，実装することができます．

実装例（C++，ACL/segtree使用）