Sorting a Sequence 5

The sortedness of a sequence $A$ of length $N$ is the number of pairs $(i,j)$ such that $1 \leq i < j \leq N$ and $A_i < A_j$.

Perform exactly $K$ operations. In each operation, choose an integer $p$ with $1 \leq p < N$ and swap $A_p$ and .

Print the maximum achievable sortedness after all operations and one operation sequence attaining it. A correct maximum alone can receive partial credit only if the submitted operation sequence follows the output format.

Each test case is assigned the point value of its subtask. A correct maximum and an operation sequence attaining it earn $100\%$. A correct maximum with a properly formatted operation sequence that does not attain it earns $50\%$. An incorrect maximum or an improperly formatted operation sequence earns $0\%$. Printing only the maximum, an incorrect number of operations, or indices outside the allowed range does not guarantee $50\%$. The subtask score is the minimum score over its test cases.

The input is given in the following format.

$N\ K$ $A_1\ A_2\ \cdots\ A_N$

Print the maximum sortedness on the first line. On each of the next $K$ lines, print the integer $p$ chosen for operation $j$ ($1 \leq j \leq K$, $$). Any optimal operation sequence is accepted.

• $2 \leq N \leq 1\,000$.
• $-10^9\leq A_i\leq10^9$ ().