\(X\) が 2 番目に大きい \(L, R\) の組数 \(f(X)\) を考える.

まず, \(X\) の位置 \(x\) を見つけ出す. あらかじめ数値がある位置を保持しておけばいい.

次に, \(x\) の左側で \(X\) より大きい数値が最初に出てくる場所 \(l_i\) を見つけ出す. これは \(f(y) = \max_{i \in [y, x]} P_i\) とすると \(f(y)\) は単調減少になるので, 最大値を保持するセグメントツリーを作って二分探索で求めることができる. さらに \(l_1\) より左側で \(X\) より大きい数値が最初に出てくる場所 \(l_2\) を見つけ出す. これも同様に二分探索を使う.

\(x\) の右側についても同様に \(r_1, r_2\) を見つけ出す.

このとき, \(X\) が 2 番目に大きい \(L, R\) は, \(l_2 \lt L \leq l_1, x \leq R \lt r_1\) または \(l_1 \lt L \leq x, r_1 \leq R \lt r_2\) であり, 組数は \(f(X) = (l_1-l_2)(r_1-x) + (x-l_1)(r_2-r_1)\) となる.

これをすべての \(X\) について計算し, \(\sum X f(X)\) を求める.