WTF Transformation

You are given an array $A$ of $N$ integers, indexed from $A[1]$ to $A[N]$, and an integer $R$.

A second array $ID$ holds $N + 1$ integers, indexed from $ID[1]$ to $ID[N+1]$, and every one of them lies in the interval $[1, N-1]$.

The Warshall-Turing-Fourier transformation of $A$ under $ID$ is the following algorithm. (The transformation is made up. It does not exist outside this problem.)

sum = 0

for i = 1 to N
    index = min(ID[i], ID[i+1])
    sum = sum + A[index]
    rotate A to the right by R places

negate every element of A

for i = 1 to N
    index = max(ID[i], ID[i+1]) + 1
    sum = sum + A[index]
    rotate A to the right by R places

Rotating $A$ to the right by $R$ places moves the element at position $j$ to position $((j + R - 1) \bmod N) + 1$. Both loops read and rotate the same array, so each rotation carries into the next step, and the sign change applies to the array as it stands after the first loop.

Every value of $ID$ is at most $N - 1$, so the index $\max(ID[i], ID[i+1]) + 1$ never leaves the interval $[1, N]$.

You know $A$ and $R$, but not $ID$. Find the largest value of sum that a choice of $ID$ can produce.

The first line contains the integers $N$ and $R$ ($2 \le N \le 3000$, $1 \le R < N$).

The second line contains $N$ integers, $A[1]$ to $A[N]$, each from the interval $[-10^4, 10^4]$.

On the first line, print the largest value of sum.

On the second line, print the $N + 1$ integers $ID[1]$ to $ID[N+1]$ that reach this value, separated by single spaces. Several arrays may reach it, so print the lexicographically smallest one: among the arrays that reach the maximum, take the one with the smallest $ID[1]$; if several remain, take the one with the smallest $ID[2]$, and continue in the same way.