题目描述

题目译自 COCI2014-2015 CONTEST #6 T6「WTF」。

你有一个长度为 $N$ 的数组 $\textbf A$，一个值域在 $[1,N-1]$ 上的长度为 $N+1$ 的数组 $\textbf{ID}$ 和一个整数 $R$。

我们通过以下伪代码对数组 $\textbf A$ 进行 Warshall-Turing-Fourier 变换：

sum = 0
for i = 1 to N
	index = min{ ID[i], ID[i+1] }
	sum = sum + A[index]
	Rotate(A, R)

Change(A)

for i = 1 to N
	index = max{ ID[i], ID[i+1] }
	index = index + 1
	sum = sum + A[index]
	Rotate(A, R)

其中：

• $\texttt{Change}(\textbf A)$ 表示把数组 $\textbf A$ 中所有元素分别改成它们的相反数。
• $\texttt{Rotate}(\textbf A,R)$ 表示把两个数组 $\textbf A$ 首尾相接得到数组 $\textbf B$，取 $\textbf B[N-R+1,2N-R]$ 代替数组 $\textbf A$。
  即向右旋转 $R$ 个位置。

你已经知道数组 $\textbf A$ 和整数 $R$，但你并不知道数组 $\textbf{ID}$。

你需要求出 WTF 变换后伪代码中 $\text{sum}$ 可能的最大值。

输入格式

第一行两个整数 $N,R$。

接下来一行 $N$ 个整数，表示数组 $\textbf A$。

输出格式

第一行一个整数，即伪代码中 $\text{sum}$ 可能的最大值。

第二行 $N+1$ 个整数，即使得 $\text{sum}$ 值最大的 $\textbf{ID}$ 数组。

如果存在多组解，输出任意一种。

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

数据范围与提示

本题采用 Special Judge。如果输出只有第一行正确，可以得到 $50\%$ 的分数，但你必须保证第二行有 $n+1$ 个符合要求的数。

• 对于 $20\%$ 的数据，有 $N\le 7$。
• 对于 $60\%$ 的数据，有 $N\le 300$。
• 对于 $100\%$ 的数据，有 $2\le N\le 3\times 10^3$，$1\le R\le N$，$\textbf A[i]\in[-10^4,10^4]$。

你需要保证你构造的 $\textbf{ID}[i]\in[1,N-1]$。