各要素が相異なる列の連続部分列の上位 \(2\) つの位置としてあり得るものの個数は、列の長さに対して線形です。具体的には、次の補題が成り立ちます。

補題.

正整数 \(N\) と \((1,2,\dots, N)\) の順列 \(P\) を任意に取る。 \(1\le L\le R\le N\) に対して、整数 \(a, b\) を \(P_L,P_{L+1},\dots, P_{R}\) のうち最も小さいものとその次に小さいものがそれぞれ \(P_a,P_b\) となるように定義したとき、 \((a,b)\) としてあり得るものの個数は \(\Theta(N)\) である。

このことは \(a\neq b\) である \((a,b)\) に対する半開区間 \([\min(a,b),\max(a,b))\) 全体の集合が laminar であることから従います。

まず、あり得る \((a,b)\) をすべて列挙します。\((L,R)=(1,N)\) からはじめて、対応する \((a,b)\) が異なるように \((L,R)\) を区間として縮めて再帰的に処理すればよく、これはセグメント木などを用いて \(O(N\log N)\) 時間で行うことができます。

また、\(f(L,R)\) を定義通りに再帰的に計算するとき、深さが \(1\) 以上の再帰段階では \((L,R)\) としてあり得るものの個数が \(O(N)\) であるため、一度計算した \(f(L,R)\) をメモして再計算を省略することが効果的です。この方法で、あり得るすべての \((a,b)\) に対する \(f(\min(a,b)+1,\max(a,b)-1)+1\) を計算しておきます。

次に、あり得るすべての \((a,b)\) に対して、それが対応するような \((L,R)\) の個数を求めます。これは単に閉区間 \([L,R]\) が閉区間 \([\min(a,b),\max(a,b)]\) を含んでいて、さらに \(P_b\) より小さな要素を \(P_a\) 以外に含まないような \((L,R)\) の個数を求めれば良く、セグメント木上の二分探索などを用いて高速に求めることができます。

最後に、\(k=f(\min(a,b)+1,\max(a,b)-1)+1\) に対する答えに \((L,R)\) の個数を足し込んでいけば、すべての \((L,R)\) に対する \(f(L,R)\) の分布、すなわち求めるものを計算することができます。

以上の解法は \(O(N\log N)\) 時間で動作します。