410232: GYM103987 H Chipmunk Sorting

There are $$$n$$$ chipmunks standing in a row. The height of the $$$i$$$-th one is indicated as $$$h_i\ (1\le i\le n)$$$. It is guaranteed that array $$$h$$$ is a permutation of length $$$n$$$. Recall that a permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order.

Awson wants to sort the chipmunks by height in increasing order. Each time he can select the $$$i$$$-th and the $$$j$$$-th chipmunk satisfying $$$i<j$$$ and $$$h_i>h_j$$$, and swap them. He will keep doing that until all chipmunks are sorted.

Awson also noticed that when swaping two chipmunks, each chipmunk whose position and height are both between them will get $$$a$$$ happiness. Formally speaking, for all integers $$$k\in(i,j)$$$, the happiness of the $$$k$$$-th chipmunk will increase by $$$a$$$ if and only if $$$h_i>h_k>h_j$$$. Note that $$$a$$$ can be negative.

Awson wants to maximize the total happiness of all chipmunks. Can you tell him the maximum happiness he can get if he swaps optimally?

The first line contains two integers $$$n\ (1\le n\le 2\cdot 10^5)$$$ and $$$a\ (a\in\{-1,1\})$$$, as described above.

The next line contains $$$n$$$ integers separated by spaces, the $$$i$$$-th of which indicates the height of the $$$i$$$-th chipmunk $$$h_i\ (1\le h_i\le n)$$$.

Print an integer representing the maximum sum of happiness of all chipmunks.

The problem contains several subtasks. You can get the corresponding score for each passed test case.

• Subtask 1 ($$$20$$$ points): $$$a=-1$$$.
• Subtask 2 ($$$40$$$ points): $$$a=1$$$ and $$$n\le 5\cdot 10^3$$$.
• Subtask 3 ($$$40$$$ points): no additional constraints.

3 1
1 2 3

0

5 -1
5 2 3 4 1

0

6 1
6 5 1 4 2 3

4

In the first example, the chipmunks are already sorted. No happiness is gained, so the answer is $$$0$$$.

In the second example, it would better not swap the the first and the last chipmunk, or the chipmunks in the middle would be unhappy.

In the third example, one of the best strategies is as follows (the swapped two are marked bold, and chipmunks that can get happiness are underlined):

$$$$$$ [6,\color{red}{\textbf{5}},1,\underline{4},\color{red}{\textbf{2}},3] \rightarrow [\color{red}{\textbf{6}},2,1,\underline{4},\underline{5},\color{red}{\textbf{3}}] \rightarrow [\color{red}{\textbf{3}},\underline{2},\color{red}{\textbf{1}},4,5,6] \rightarrow [1,2,3,4,5,6] $$$$$$

At last, the $$$6$$$ chipmunks get $$$0,1,0,2,1,0$$$ happiness respectively, so the total happiness is $$$4$$$.