Problem Description

You are given an array $\textbf A$ of length $n$, an array $\textbf{ID}$ of length $n+1$ with value range $[1,n-1]$, and an integer $r$.

We apply a Warshall-Turing-Fourier transform $^\textsf{[1]}$ to array $\textbf A$ using the following pseudocode:

sum = 0
for i = 1 to n
	index = min{ID[i], ID[i+1]}
	sum = sum + A[index]
	Rorate(A, r)
Change(A)
for i = 1 to n
	index = max{ID[i], ID[i+1]}
	index = index + 1
	sum = sum + A[index]
	Rorate(A, r)

Where:

• $\texttt{Change}(\textbf A)$ means changing every element in array $\textbf A$ to its opposite number.
• $\texttt{Rorate}(\textbf A, r)$ means copying array $\textbf A$ twice to obtain array $\textbf B$, and replacing $\textbf A$ with $\textbf B[n-r+1,2n-r]$.
  That is, rotate right by $r$ positions.

You already know array $\textbf A$ and integer $r$, but you do not know array $\textbf{ID}$.

You need to find the maximum possible value of $\text{sum}$ in the pseudocode after the WTF transform.

$\textsf{[1]}$: It does not actually exist. Of course, it can also be called the "Sept transform".

Input Format

The first line contains two integers $n, r$.

The next line contains $n$ integers, representing array $\textbf A$.

Output Format

The first line contains one integer, the maximum possible value of $\text{sum}$ in the pseudocode.

The second line contains $n+1$ integers, the array $\textbf{ID}$ that makes $\text{sum}$ as large as possible.

If there are multiple solutions, output any one of them.

5 3
1 -1 1 -1 1

10
1 1 1 2 2 3

6 5
2 5 4 1 3 5

16
3 2 1 1 5 4 1

Hint

Scoring

If only the first line of your output is correct, you can get $50\%$ of the score.

But you must ensure that the second line has $\bm{n+1}$ numbers that satisfy the requirements.

Constraints

This problem uses Special Judge.

• For $20\%$ of the testdata, $n \le 7$.
• For $60\%$ of the testdata, $n \le 300$.
• For $100\%$ of the testdata, $2 \le n \le 3 \times 10^3$, $1 \le r \le n$, $\textbf A[i] \in [-10^4, 10^4]$.

You must ensure that your constructed $\textbf{ID}[i] \in [1,n-1]$.

Notes

According to the original problem settings, the full score is 160 points.

Translated from COCI 2014-2015 Contest #6 Task F WTF.

Translated by ChatGPT 5