WTF 변환

정수 $N$개로 이루어진 배열 $A$와 정수 $R$이 주어진다. $A$의 원소에는 $A[1]$부터 $A[N]$까지 번호가 붙어 있다.

배열 $ID$는 정수 $N + 1$개로 이루어지고 $ID[1]$부터 $ID[N+1]$까지 번호가 붙어 있으며, 모든 원소가 $[1, N-1]$ 구간에 들어간다.

$ID$를 사용한 $A$의 Warshall-Turing-Fourier 변환은 다음 알고리즘이다. (이 변환은 지어낸 것이고 이 문제 밖에서는 존재하지 않는다.)

sum = 0

for i = 1 to N
    index = min(ID[i], ID[i+1])
    sum = sum + A[index]
    A를 오른쪽으로 R칸 회전한다

A의 모든 원소의 부호를 바꾼다

for i = 1 to N
    index = max(ID[i], ID[i+1]) + 1
    sum = sum + A[index]
    A를 오른쪽으로 R칸 회전한다

$A$를 오른쪽으로 $R$칸 회전하면 위치 $j$에 있던 원소가 위치 $((j + R - 1) \bmod N) + 1$로 옮겨간다. 두 반복문은 같은 배열을 읽고 회전시키므로 회전 결과가 다음 단계로 이어지고, 부호를 바꾸는 연산도 첫 반복문이 끝난 시점의 배열에 적용된다.

$ID$의 모든 원소는 $N - 1$ 이하이므로 $\max(ID[i], ID[i+1]) + 1$은 항상 $[1, N]$ 구간 안에 있다.

$A$와 $R$은 알지만 $ID$는 모른다. $ID$를 골라서 만들 수 있는 sum의 최댓값을 구하라.

첫째 줄에 정수 $N$과 $R$이 주어진다. ($2 \le N \le 3000$, $1 \le R < N$)

둘째 줄에 $A[1]$부터 $A[N]$까지 정수 $N$개가 주어진다. 각 원소는 $[-10^4, 10^4]$ 구간의 정수다.

첫째 줄에 sum의 최댓값을 출력한다.

둘째 줄에 그 최댓값을 만드는 $ID[1]$부터 $ID[N+1]$까지 정수 $N + 1$개를 공백 한 칸으로 구분해 출력한다. 최댓값을 만드는 배열이 여러 개면 사전순으로 가장 앞서는 것을 출력한다. 즉 최댓값을 만드는 배열 중에서 $ID[1]$이 가장 작은 것을 고르고, 그런 배열이 여럿이면 $ID[2]$가 가장 작은 것을 고르는 식으로 정한다.