For convenience, let us consider everything using \(0\)-based indices. Incrementing each \(A_i\) yields the same score.

Instead of directly counting descents, let us consider solving the following problem.

• Fix \(K\) (\(1 \leq K \leq N\)). Consider ways of partitioning the \(A_i\) into \(K\) sets \((y_{0,0},\ldots,y_{0,s_0-1}),\ldots,(y_{K-1,0},\ldots,y_{K-1,s_{K-1}-1})\), where each \(y_i\) is in ascending order. Hereafter, these \(y_i\) are called blocks. Let \(x\) be the sequence obtained by concatenating all the blocks, and find the sum of the scores of \(x\) over all partitions.

If we can solve the above problem for each \(1 \leq K \leq N\), we can obtain the answer to the original problem from it.

Let us reinterpret the score in the following form.

• For each \(A_i\), either attach a link to some element to its left, or do nothing. If nothing is done, the weight of the element is multiplied by \(A_i\). Such an element is called a terminal element.

For an element \(v\), the terminal element reached by following links from \(v\) is called the root of \(v\). The set of elements whose root is element \(r\) is called the group of \(r\).

Suppose we have fixed which elements are terminal elements and all their groups. Conversely, we have not fixed which block each element belongs to, nor the specific way links are attached. Let us consider what the sum of scores becomes when we let all of these vary.

First, this problem can be considered independently for each group.

So, let us focus on one terminal element \(v\). Within \(v\)’s group, let \(a\) be the count of values at least \(v+1\), and \(b\) be the count of values at most \(v-1\).

Suppose \(v\) is placed in block \(k\). Each value at least \(v+1\) is assigned to one of blocks \(k,k+1,\ldots,K-1\). Each value at most \(v-1\) is assigned to one of blocks \(k+1,\ldots,K-1\). Thus, there are a total of \((K-k)^a(K-k-1)^b\) ways to distribute the group’s elements to blocks. And for each of these, there are \((a+b)!\) ways to attach the links.

This gives us the sum of scores when the terminal elements and grouping are fixed.

Now, let us consider taking the sum over all choices of terminal elements and groupings. This can be done by considering the following DP.

• \(dp[h][C][D]=\) the sum of scores when the terminal elements among the top \(N-h\) elements have already been decided, there are \(C\) elements among the top \(N-h\) whose group has not yet been decided, and there are \(D\) elements among the bottom \(h\) whose group has not yet been decided.

We compute this while moving \(h=N,N-1,N-2,\ldots,0\).

Here, we must be careful about how \(D\) is handled. Since we decrease \(h\), we are tempted to keep track of which of the bottom \(h\) values are used and which are not. That is, we are tempted to keep \(dp[h][C][s]\) for a subset \(s\) of the bottom \(h\) values. However, it turns out that the only information about \(s\) that matters is its size. That is, if two sets \(s\) and \(t\) satisfy \(|s|=|t|\), we have \(dp[h][C][s]=dp[h][C][t]\). This can be understood by considering what this counting is doing.

Let us consider the concrete transitions. The difficult part is the transition \(dp[h+1] \to dp[h]\) in which \(A_h\) is used as a terminal element. Considering the transition where \(a\) elements from above and \(b\) elements from below are placed into \(A_h\)’s group,

\[dp[h][C-a][D-b] \mathrel{+}= dp[h+1][C][D+1] \times {C \choose a} \times {h-D+b \choose b} \times (a+b)! \times \left ( \sum_{0 \leq k < K}(K-k)^a (K-k-1)^b \right ).\]

This is slow if done naively, but it can be sped up using FFT, allowing the transition to be performed in \(O(N^2 \log N)\) time. Thus, the overall solution runs in \(O(N^4 \log N)\) time.

Sample Solution (C++)