Without loss of generality, assume \(A_1 \geq A_2 \geq \cdots \geq A_N\).

Let us consider the problem where \(p\) is fixed. The solution to this version is as follows.

• Let \(x_1,x_2,\cdots,x_N\) be the sorted list of cards in ascending order of \(p_i\). Then, do the operation below for each \(i=1,3,\cdots,N-1\). Here, \(s\) is a priority queue, and \(ans\) is a variable that stores the answer.
  • Add \(A_{x_i}\) and \(A_{x_{i+1}}\) to \(s\).
  • Take out the largest element from \(s\) and add it to \(ans\).

Now, let us unfix \(p\) and solve the counting problem. For each \(1 \leq k \leq N\), we want to know the number of times \(A_k\) is added to \(ans\). Almost similarly, let us find the number of times a value greater than or equal to \(A_k\) is added to \(ans\).

Let us classify the elements of the sequence \(x\) by whether \(x_i \leq k\) or not to make a \(01\) sequence \(y\), where an element such that \(x_i \leq k\) corresponds to \(1\). Enumerating all \(N!\) permutations \(p\) is equivalent to enumerating all \(01\) sequences \(y\) containing \(N-k\) zeros and \(k\) ones. Here, the same \(01\) sequence appears \((N-k)!k!\) times.

For a fixed \(y\), we can find the number of times a value greater than or equal to \(A_k\) is added to \(ans\), as follows.

• Let \(cnt(i)\) denote the number of \(1\)s in the last \(i\) elements of \(y\).
• Then, the number of times a value greater than or equal to \(A_k\) is added to \(ans\) is \(k-\max_{i=0,2,4,\cdots,N}(cnt(i)-i/2)\).

This follows from the number of values greater than or equal to \(A_k\) in the priority queue.

The essentially difficult part is \(\max_{i=0,2,4,\cdots,N}(cnt(i)-i/2)\). First, let us make a \(-1,1\) sequence \(y'\) by replacing \(0\) with \(-1\). Then, if we let \(suf(i)\) denote the sum of the last \(i\) elements of \(y'\), we have \(\max_{i=0,2,4,\cdots,N}(cnt(i)-i/2)=\lfloor \max_{0 \leq i \leq N}suf(i)/2 \rfloor\). Note that the range of \(i\) at \(\max\) on the right side is not limited to even numbers.

Let us fix the value \( \max_{0 \leq i \leq N}suf(i)\) to \(h\) and count \(y'\) that realize it. First, let \(m\) be the largest \(i\) that maximizes \(suf(i)\). Here, let us reverse the last \(m\) elements of \(y'\) and flip the signs of those elements. Let \(z\) be the resulting sequence. Then, \(z\) will satisfy the following conditions:

• the sum of \(z\) is \(2k-N-2h\);
• all prefix sums of \(z\) are at least \(2k-N-2h\).

On the other hand, if we have a sequence \(z\) that satisfies the two conditions above, there is a unique \(y'\) that corresponds to it. Thus, instead of counting \(y'\), let us count \(z\).

The number of \(z\) can be written as a simple formula with binomial coefficients, similar to the formula that gives Catalan numbers, which subtracts the number of paths symmetric to invalid paths. Now, we just have to unfix \(h\) and compute the sum of this formula. Using prefix sums, the computation for each \(k\) can be done in \(O(1)\) time, after a pre-computation that takes \(O(N)\) time.

The total complexity is \(O(N)\).