P7959 [COCI 2014/2015 #6] WTF

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: ```cpp 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".

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

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.**

#### 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](https://hsin.hr/coci/archive/2014_2015/)** [Contest #6](https://hsin.hr/coci/archive/2014_2015/contest6_tasks.pdf) Task F _**WTF**_. Translated by ChatGPT 5