一般性を失わず，\(A_1 \geq A_2 \geq \cdots \geq A_N\) であるとします．

\(p\) が固定された場合の問題を考えます． この時の解法は次のようになります．

• \(p_i\) の昇順にカードを並べ，その番号を \(x_1,x_2,\cdots,x_N\) とする．その後，\(i=1,3,\cdots,N-1\) に対して以下の操作を行う．なお，\(s\) は優先度付きキュー，\(ans\) は答えを表す変数である．
  • \(s\) に \(A_{x_i}\) と \(A_{x_{i+1}}\) を追加する．
  • \(s\) から最大の要素を取り出し，\(ans\) に加算する．

次に，\(p\) を動かして数え上げを解きます． 各 \(1 \leq k \leq N\) について，\(ans\) に \(A_k\) が足される回数が分かればいいです． ここでは，ほとんど同じことですが，\(ans\) に \(A_k\) 以上の値が足される回数を求めることにします．

数列 \(x\) の各要素を，\(x_i \leq k\) であるか否かで分類し，\(01\) 列 \(y\) を作ることにします．\(x_i \leq k\) である要素を \(1\) に対応させます． \(p\) を \(N!\) 通り試すことは，\(0\) を \(N-k\) 個，\(1\) を \(k\) 個含む \(01\) 列 \(y\) をすべて試すことに対応します．ただし，同じ \(01\) 列が \((N-k)!k!\) 回登場します．

\(y\) を一つ決め打った時，\(ans\) に \(A_k\) 以上の値が足される回数は次のように求められます．

• \(y\) の後ろ \(i\) 個にある \(1\) の個数を \(cnt(i)\) で表す．
• この時，\(k-\max_{i=0,2,4,\cdots,N}(cnt(i)-i/2)\) 回，\(ans\) に \(A_k\) 以上の値が足される．

これは，優先度付きキューに入っている \(A_k\) 以上の値の個数を考えるとわかります．

\(\max_{i=0,2,4,\cdots,N}(cnt(i)-i/2)\) の部分が本質的に難しい部分です． まず，\(0\) を \(-1\) に変換することで，\(-1,1\) 列 \(y'\) を作ります． \(y'\) の後ろ \(i\) 個の和を \(suf(i)\) で表すと， \(\max_{i=0,2,4,\cdots,N}(cnt(i)-i/2)=\lfloor \max_{0 \leq i \leq N}suf(i)/2 \rfloor\) が成り立ちます．右辺の \(\max\) の \(i\) の値域は偶数に限定されないことに注意してください．

\( \max_{0 \leq i \leq N}suf(i)\) の値を決め打ち，\(h\) であるとします． この時条件を満たす \(y'\) の個数を数えてみます． まず，\(suf(i)\) を最大化する \(i\) のうち，最大のものを \(m\) とおきます． ここで，\(y'\) の後ろ \(m\) 項について，それらを左右反転し，さらに \(-1,1\) を入れ替えたとします． こうして得た数列を \(z\) とおきます． ここで \(z\) は，以下の条件を満たす数列です．

• \(z\) の総和は \(2k-N-2h\)
• \(z\) の prefix-sum は，すべて \(2k-N-2h\) 以上である．

ここで逆に，上記の \(2\) 条件を満たす \(z\) があれば，対応する \(y'\) を一意に決定することが可能です． よって，\(y'\) の個数を求める代わりに，\(z\) の個数を数えればよいです．

\(z\) の個数は，カタラン数の式を求めるのと同様に，鏡写しにしたパスの個数を引くことを考えれば，簡単なコンビネーションの式で書けます．あとは，\(h\) を動かしてここで得た式の和を取ればよいですが，これは累積和を使えば，\(k\) に寄らない前計算 \(O(N)\) 時間，各 \(k\) あたり \(O(1)\) 時間で計算できます．

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