The company "Divan's Sofas" is planning to build $n + 1$ different buildings on a coordinate line so that:

the coordinate of each building is an integer number;

no two buildings stand at the same point.

Let $x_i$ be the coordinate of the $i$-th building. To get from the building $i$ to the building $j$, Divan spends $|x_i - x_j|$ minutes, where $|y|$ is the absolute value of $y$.

All buildings that Divan is going to build can be numbered from $0$ to $n$. The businessman will live in the building $0$, the new headquarters of "Divan's Sofas". In the first ten years after construction Divan will visit the $i$-th building $a_i$ times, each time spending $2 \cdot |x_0-x_i|$ minutes for walking.

Divan asks you to choose the coordinates for all $n + 1$ buildings so that over the next ten years the businessman will spend as little time for walking as possible.


-----Input-----

Each test contains several test cases. The first line contains one integer number $t$ ($1 \le t \le 10^3$) — the number of test cases.

The first line of each case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of buildings that "Divan's Sofas" is going to build, apart from the headquarters.

The second line contains the sequence $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^6$), where $a_i$ is the number of visits to the $i$-th building.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, on the first line print the number $T$ — the minimum time Divan will spend walking.

On the second line print the sequence $x_0, x_1, \ldots, x_n$ of $n + 1$ integers, where $x_i$ ($-10^6 \le x_i \le 10^6$) is the selected coordinate of the $i$-th building. It can be shown that an optimal answer exists with coordinates not exceeding $10^6$.

If there are multiple answers, print any of them.


-----Examples-----

Input
4
3
1 2 3
5
3 8 10 6 1
5
1 1 1 1 1
1
0
Output
14
2 4 1 3
78
1 -1 0 2 3 4
18
3 6 1 5 2 4
0
1 2


-----Note-----

Let's look at the first example.

Divan will visit the first building $a_1 = 1$ times, the second $a_2 = 2$ times and the third $a_3 = 3$ times. Then one of the optimal solution will be as follows:

the headquarters is located in $x_0 = 2$;

$x_1 = 4$: Divan will spend $2 \cdot |x_0-x_1| \cdot a_1 = 2 \cdot |2-4| \cdot 1 = 4$ minutes walking to the first building;

$x_2 = 1$: Divan will spend $2 \cdot |x_0-x_2| \cdot a_2 = 2 \cdot |2-1| \cdot 2 = 4$ minutes walking to the second building;

$x_3 = 3$: Divan will spend $2 \cdot |x_0-x_3| \cdot a_3 = 2 \cdot |2-3| \cdot 3 = 6$ minutes walking to the third building.

In total, Divan will spend $4 + 4 + 6 = 14$ minutes. It can be shown that it is impossible to arrange buildings so that the businessman spends less time.

Among others, $x = [1, 3, 2, 0]$, $x = [-5, -3, -6, -4]$ are also correct answers for the first example.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Constructive algorithms


Solutions:
class Input:

	def __init__(self, file=''):
		self.file = file
		if file:
			self.f = open(file, 'r')
			self.read = self.f.readline
		else:
			self.read = input
inp = Input('')
t = int(inp.read())
for _ in range(t):
	n = int(inp.read())
	a = list(map(int, inp.read().split(' ')))
	sorted_id = sorted(list(range(n)), key=lambda x: a[x], reverse=True)
	out_sum = sum([a[sorted_id[i]] * (i // 2 + 1) * 2 for i in range(n)])
	order = [i + 1 for i in list(reversed(sorted_id[1::2]))] + [0] + [j + 1 for j in sorted_id[::2]]
	out_arr = sorted(list(range(n + 1)), key=lambda x: order[x])
	print(out_sum)
	print(*out_arr)


def solve():
	for t in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		a = [[arr[i], i] for i in range(len(arr))]
		a.sort(key=lambda x: x[0], reverse=True)
		mid = (n + 2) // 2
		left = mid - 1
		right = mid + 1
		isleft = True
		ans = [None] * n
		res = 0
		for i in range(n):
			(cnt, idx) = (a[i][0], a[i][1])
			if isleft:
				ans[idx] = left
				cost = 2 * (mid - left)
				res += cnt * cost
				left -= 1
			else:
				ans[idx] = right
				cost = 2 * (right - mid)
				res += cnt * cost
				right += 1
			isleft = not isleft
		print(res)
		print(mid, end=' ')
		for ele in ans:
			print(ele, end=' ')
		print()
solve()


import math
for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	op = sorted(list(zip(a, [i for i in range(N)])))
	l1 = [-1 for _ in range(N + 1)]
	for i in range(0, N, 2):
		l1[op[i][1] + 1] = i // 2
	count = N
	for j in range(1, N, 2):
		l1[op[j][1] + 1] = count
		count -= 1
	l1[0] = count
	tot = 0
	for i in range(1, N + 1):
		tot += 2 * abs(l1[i] - l1[0]) * a[i - 1]
	print(tot)
	print(*l1)


import sys
import bisect
import math
from collections import deque
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 9

def solve():
	n = int(input())
	b = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append([b[i], i + 1])
	queue = deque()
	queue.append(0)
	a.sort(reverse=True)
	for i in range(0, n, 2):
		queue.append(a[i][1])
	for i in range(1, n, 2):
		queue.appendleft(a[i][1])
	a = [x for x in queue]
	arr = [0] * (n + 1)
	for i in range(n + 1):
		arr[a[i]] = i
	ans = 0
	for i in range(1, n + 1):
		ans += 2 * abs(arr[i] - arr[0]) * b[i - 1]
	return str(ans) + '\n' + ' '.join((str(x) for x in arr))
t = 1
t = int(input())
for _ in range(t):
	print(solve())