There are $n$ students at your university. The programming skill of the $i$-th student is $a_i$. As a coach, you want to divide them into teams to prepare them for the upcoming ICPC finals. Just imagine how good this university is if it has $2 \cdot 10^5$ students ready for the finals!

Each team should consist of at least three students. Each student should belong to exactly one team. The diversity of a team is the difference between the maximum programming skill of some student that belongs to this team and the minimum programming skill of some student that belongs to this team (in other words, if the team consists of $k$ students with programming skills $a[i_1], a[i_2], \dots, a[i_k]$, then the diversity of this team is $\max\limits_{j=1}^{k} a[i_j] - \min\limits_{j=1}^{k} a[i_j]$).

The total diversity is the sum of diversities of all teams formed.

Your task is to minimize the total diversity of the division of students and find the optimal way to divide the students.


-----Input-----

The first line of the input contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of students.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the programming skill of the $i$-th student.


-----Output-----

In the first line print two integers $res$ and $k$ — the minimum total diversity of the division of students and the number of teams in your division, correspondingly.

In the second line print $n$ integers $t_1, t_2, \dots, t_n$ ($1 \le t_i \le k$), where $t_i$ is the number of team to which the $i$-th student belong.

If there are multiple answers, you can print any. Note that you don't need to minimize the number of teams. Each team should consist of at least three students.


-----Examples-----
Input
5
1 1 3 4 2

Output
3 1
1 1 1 1 1 

Input
6
1 5 12 13 2 15

Output
7 2
2 2 1 1 2 1 

Input
10
1 2 5 129 185 581 1041 1909 1580 8150

Output
7486 3
3 3 3 2 2 2 2 1 1 1 



-----Note-----

In the first example, there is only one team with skills $[1, 1, 2, 3, 4]$ so the answer is $3$. It can be shown that you cannot achieve a better answer.

In the second example, there are two teams with skills $[1, 2, 5]$ and $[12, 13, 15]$ so the answer is $4 + 3 = 7$.

In the third example, there are three teams with skills $[1, 2, 5]$, $[129, 185, 581, 1041]$ and $[1580, 1909, 8150]$ so the answer is $4 + 912 + 6570 = 7486$.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Sorting

Greedy algorithms


Solutions:
n = int(input())
arr = list(map(int, input().split()))
for i in range(n):
	arr[i] = (arr[i], i)
arr.sort()
dp = [999999999999] * (n + 1)
dp[0] = 0
came_from = [-1] * (n + 1)
for i in range(n):
	if i + 3 <= n:
		if dp[i] + arr[i + 2][0] - arr[i][0] < dp[i + 3]:
			came_from[i + 3] = i
			dp[i + 3] = min(dp[i + 3], dp[i] + arr[i + 2][0] - arr[i][0])
	if i + 4 <= n:
		if dp[i] + arr[i + 3][0] - arr[i][0] < dp[i + 4]:
			came_from[i + 4] = i
			dp[i + 4] = min(dp[i + 4], dp[i] + arr[i + 3][0] - arr[i][0])
	if i + 5 <= n:
		if dp[i] + arr[i + 4][0] - arr[i][0] < dp[i + 5]:
			came_from[i + 5] = i
			dp[i + 5] = min(dp[i + 5], dp[i] + arr[i + 4][0] - arr[i][0])
result = [0] * n
i = n
team = 1
while i > 0:
	target = came_from[i]
	while i > target:
		result[arr[i - 1][1]] = team
		i -= 1
	team += 1
print(dp[n], team - 1)
print(*result, sep=' ')


inf = float('inf')

def f(A, T):
	dp = [0] * len(A)
	for i in range(len(A) - 1, -1, -1):
		if len(A) - i < 3:
			dp[i] = inf
		elif len(A) - i == 3:
			dp[i] = A[i + 2][0] - A[i][0]
			T[i] = len(A)
		else:
			extend = dp[i + 1] + (A[i + 1][0] - A[i][0])
			start = A[i + 2][0] - A[i][0] + dp[i + 3]
			if extend < start:
				dp[i] = extend
				T[i] = T[i + 1]
			else:
				dp[i] = start
				T[i] = i + 3
	return dp[0]
n = int(input())
rest = map(int, input().split())
A = []
for (i, a) in enumerate(rest):
	A.append((a, i))
A.sort(key=lambda x: x[0])
T = [0] * len(A)
ans = f(A, T)
X = [0] * len(A)
team = 0
index = 0
while index != len(A):
	nxt = T[index]
	for k in range(index, nxt):
		(_, idx) = A[k]
		X[idx] = team + 1
	team += 1
	index = nxt
print(ans, team)
print(' '.join(map(str, X)))


def main():
	n = int(input())
	a = readIntArr()
	a2 = [[x, i + 1] for (i, x) in enumerate(a)]
	a2.sort(key=lambda x: x[0])
	dp = [inf for _ in range(n)]
	dp2 = [inf for _ in range(n)]
	dp2i = [-1 for _ in range(n)]
	for i in range(2, min(n, 5)):
		dp[i] = a2[i][0] - a2[0][0]
		dp2[i] = dp[i - 1] - a2[i][0]
		dp2i[i] = i
		if dp2[i] >= dp2[i - 1]:
			dp2i[i] = dp2i[i - 1]
			dp2[i] = dp2[i - 1]
	for i in range(5, n):
		dp2[i] = dp[i - 1] - a2[i][0]
		dp2i[i] = i
		if dp2[i] >= dp2[i - 1]:
			dp2i[i] = dp2i[i - 1]
			dp2[i] = dp2[i - 1]
		dp[i] = a2[i][0] + dp2[i - 2]
	minDiversity = dp[n - 1]
	groups = []
	right = n - 1
	while True:
		left = dp2i[right - 2]
		if left == -1:
			left = 0
		temp = []
		for i in range(left, right + 1):
			temp.append(a2[i][1])
		groups.append(temp)
		if left == 0:
			break
		right = left - 1
	nGroups = len(groups)
	grouping = [-1 for _ in range(n)]
	for i in range(nGroups):
		for student in groups[i]:
			grouping[student - 1] = i + 1
	print('{} {}'.format(minDiversity, nGroups))
	oneLineArrayPrint(grouping)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import sys
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__

class SegmTree:

	def __init__(self, size):
		N = 1
		while N < size:
			N <<= 1
		self.N = N
		self.tree = [(float('inf'), -1)] * (2 * self.N)

	def build(self):
		for i in range(self.N - 1, 0, -1):
			self.tree[i] = min(self.tree[i << 1], self.tree[i << 1 | 1])

	def modify(self, i, value):
		i += self.N
		self.tree[i] = (value, i - self.N)
		while i > 1:
			self.tree[i >> 1] = min(self.tree[i], self.tree[i ^ 1])
			i >>= 1

	def query_range(self, l, r):
		l += self.N
		r += self.N
		result = (float('inf'), -1)
		while l < r:
			if l & 1:
				result = min(result, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				result = min(result, self.tree[r])
			l >>= 1
			r >>= 1
		return result
n = int(input())
a = list(map(int, input().split()))
if n < 6:
	print(max(a) - min(a), 1)
	ans = [1] * n
	print(*ans)
	sys.exit()
pos = {}
for (i, val) in enumerate(a):
	if val not in pos:
		pos[val] = []
	pos[val].append(i)
a.sort()
jump = []
for i in range(n - 1):
	jump.append(a[i + 1] - a[i])
totalSum = a[-1] - a[0]
st = SegmTree(n - 1)
for i in range(2, min(5, n - 1 - 2)):
	st.modify(i, totalSum - jump[i])
prevSep = [-1] * (n - 1)
for i in range(5, n - 1 - 2):
	(leftMin, sep) = st.query_range(2, i - 2)
	newVal = leftMin - jump[i]
	prevSep[i] = sep
	st.modify(i, newVal)
(res, sep) = st.tree[1]
seps = []
while sep > -1:
	seps.append(sep)
	sep = prevSep[sep]
team = 1
ans = [None] * n
for (i, val) in enumerate(a):
	p = pos[val].pop()
	ans[p] = team
	if seps and i == seps[-1]:
		team += 1
		seps.pop()
print(res, team)
print(*ans)


n = int(input())
inp = input().split()
d = [(int(inp[i]), i) for i in range(n)]
d.sort()
mmm = d[-1][0] - d[0][0]
dif = [d[i + 1][0] - d[i][0] for i in range(n - 1)]
if n < 6:
	print(sum(dif), 1)
	print('1 ' * n)
	exit()
dp = [-1] * (n - 1)
dpp = [-1] * (n - 1)
ninf = -10000000000
dp[0] = ninf
dp[1] = ninf
dp[2] = dif[2]
dp[3] = dif[3]
dp[4] = dif[4]
dpp[0] = -1
dpp[1] = -1
dpp[2] = -1
dpp[3] = -1
dpp[4] = -1
for i in range(5, n - 1):
	ans = -1
	src = -1
	for j in range(3, 6):
		if i - j >= 0 and dp[i - j] + dif[i] > ans:
			ans = dp[i - j] + dif[i]
			src = i - j
	dp[i] = ans
	dpp[i] = src
ans = -1
src = -1
for j in range(n - 4, n - 7, -1):
	if dp[j] > ans:
		ans = dp[j]
		src = j
l = []
while src != -1:
	l.append(src)
	src = dpp[src]
l.reverse()
ll = [1]
lind = 0
ind = 0
team = 1
kk = len(l)
for ind in range(1, n):
	if lind < kk and l[lind] == ind - 1:
		team += 1
		lind += 1
	ll.append(team)
aaa = [0] * n
for i in range(n):
	dd = ll[i]
	aaa[d[i][1]] = dd
print(mmm - ans, team)
print(*aaa)


import math
import sys
from collections import defaultdict
from itertools import groupby
rt = lambda : map(int, input().split())
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))

def main():
	n = ri()
	a_raw = rl()
	a = [(x, i) for (i, x) in enumerate(a_raw)]
	a.sort()
	dp = [math.inf] * (n + 1)
	dp[0] = 0
	size = defaultdict(int)
	for i in range(n):
		if dp[i] == math.inf:
			continue
		if i + 3 <= n and dp[i] + a[i + 2][0] - a[i][0] < dp[i + 3]:
			dp[i + 3] = dp[i] + a[i + 2][0] - a[i][0]
			size[i + 3] = 3
		if i + 4 <= n and dp[i] + a[i + 3][0] - a[i][0] < dp[i + 4]:
			dp[i + 4] = dp[i] + a[i + 3][0] - a[i][0]
			size[i + 4] = 4
		if i + 5 <= n and dp[i] + a[i + 4][0] - a[i][0] < dp[i + 5]:
			dp[i + 5] = dp[i] + a[i + 4][0] - a[i][0]
			size[i + 5] = 5
	team = 1
	res = [0] * n
	pos = n - 1
	div = 0
	while pos >= 0:
		start = pos - size[pos + 1] + 1
		for i in range(start, pos + 1):
			res[a[i][1]] = team
		div += a[pos][0] - a[start][0]
		pos = start - 1
		if pos >= 0:
			team += 1
	print(div, team)
	print(*res)
main()


import sys
import math
from collections import defaultdict, Counter, deque
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for i in range(1):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	for j in range(n):
		l.append([a[j], j])
	l.sort()
	dp = [[10 ** 9, 0] for j in range(n + 1)]
	dp[0][0] = 0
	for j in range(n - 2):
		cur = dp[j][0] + l[j + 2][0] - l[j][0]
		if dp[j + 3][0] > cur:
			dp[j + 3] = [cur, j - 1]
		if j + 4 <= n:
			cur = dp[j][0] + l[j + 3][0] - l[j][0]
			if dp[j + 4][0] > cur:
				dp[j + 4] = [cur, j - 1]
		if j + 5 <= n:
			cur = dp[j][0] + l[j + 4][0] - l[j][0]
			if dp[j + 5][0] > cur:
				dp[j + 5] = [cur, j - 1]
	j = n - 1
	p = 1
	while j > 0:
		for k in range(j, dp[j + 1][1], -1):
			a[l[k][1]] = p
		p += 1
		j = dp[j + 1][1]
	print(dp[n][0], p - 1)
	print(*a)


n = int(input())
a = list(map(int, input().split()))
a = sorted([(num, i) for (i, num) in enumerate(a)])
INF = 10 ** 18
diff = a[-1][0] - a[0][0]
dp = [0] * (n + 1)
max_1 = 0
max_2 = 0
ind = []
for i in range(3, n - 2):
	max_1 = max(max_1, dp[i - 2])
	max_2 = max(max_2, dp[i])
	tmp1 = a[i][0] - a[i - 1][0] + max_1
	tmp2 = max_2
	if tmp1 <= tmp2:
		dp[i + 1] = tmp2
	else:
		dp[i + 1] = tmp1
		ind.append(i)
ans_ind = []
ans = diff - dp[n - 2]
for i in ind[::-1]:
	if not ans_ind:
		ans_ind.append(i)
	elif ans_ind[-1] >= i + 3:
		ans_ind.append(i)
print(ans, len(ans_ind) + 1)
pos = 0
group = 1
group_li = [0] * n
for num in ans_ind[::-1]:
	while pos < num:
		group_li[a[pos][1]] = group
		pos += 1
	group += 1
while pos < n:
	group_li[a[pos][1]] = group
	pos += 1
print(*group_li)


import sys, math, queue, collections
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
a = [(a[i], i) for i in range(n)]
a.sort()
dp = [10 ** 10 for i in range(n + 1)]
x = [0 for i in range(n)]
col = [-100 for i in range(n)]
dp[-1] = 0
for i in range(n):
	for k in range(3, 6):
		if i - k + 1 >= 0:
			if dp[i - k] + a[i][0] - a[i - k + 1][0] <= dp[i]:
				dp[i] = dp[i - k] + a[i][0] - a[i - k + 1][0]
				x[i] = i - k + 1
dp.pop()
c = 0
while len(x) > 0:
	t = x[-1]
	c += 1
	while len(x) != t:
		col[a[len(x) - 1][1]] = c
		x.pop()
print(dp[-1], c)
print(*col)


from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
l = list(map(int, input().split()))
la = []
for i in range(n):
	la.append([l[i], i])
la.sort()
dp = [(inf, 0)] * (n + 1)
dp[3] = (la[2][0] - la[0][0], 3)
if n > 3:
	dp[4] = (la[3][0] - la[0][0], 4)
if n > 4:
	dp[5] = (la[4][0] - la[0][0], 5)
for i in range(6, n + 1):
	dp[i] = min(dp[i], (dp[i - 3][0] + la[i - 1][0] - la[i - 3][0], 3))
	dp[i] = min(dp[i], (dp[i - 4][0] + la[i - 1][0] - la[i - 4][0], 4))
	dp[i] = min(dp[i], (dp[i - 5][0] + la[i - 1][0] - la[i - 5][0], 5))
m = n
ans = [0] * n
r = 0
while m != 0:
	z = dp[m]
	r += 1
	for i in range(m - z[1], m):
		ans[la[i][1]] = r
	m -= z[1]
print(dp[n][0], r)
print(*ans)


from collections import *
import sys

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
n = ri()
c = rl()
b = []
for (i, ai) in enumerate(c):
	b.append((ai, i))
b.sort()
a = []
for i in range(n):
	a.append(b[i][0])
dp = [10 ** 9 + 1] * n
group = [0] * n
dp[2] = a[2] - a[0]
dp[3] = a[3] - a[0]
dp[4] = a[4] - a[0]
for i in range(min(5, n)):
	group[i] = min(5, n)
for i in range(5, n):
	if i - 3 >= 0:
		val = dp[i - 3] + a[i] - a[i - 2]
		if val < dp[i]:
			dp[i] = val
			group[i] = 3
	if i - 4 >= 0:
		val = dp[i - 4] + a[i] - a[i - 3]
		if val < dp[i]:
			dp[i] = val
			group[i] = 4
	if i - 5 >= 0:
		val = dp[i - 5] + a[i] - a[i - 4]
		if val < dp[i]:
			dp[i] = val
			group[i] = 5
i = n - 1
team = []
ans = [-1] * n
nb = 1
while i > 0:
	if i - group[i] < 0:
		for j in range(i + 1):
			ans[b[j][1]] = nb
		nb += 1
		break
	else:
		for j in range(group[i]):
			ans[b[i - j][1]] = nb
		nb += 1
		i -= group[i]
nb -= 1
print(dp[n - 1], nb)
print(*ans)


import bisect
n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
dp = [0] * n
if n == 3:
	print(b[-1] - b[0], 1)
	print(1, 1, 1)
elif n == 4:
	print(b[-1] - b[0], 1)
	print(1, 1, 1, 1)
elif n == 5:
	print(b[-1] - b[0], 1)
	print(1, 1, 1, 1, 1)
else:
	cnt = [0] * n
	dp[2] = b[2] - b[0]
	dp[3] = b[3] - b[0]
	dp[4] = b[4] - b[0]
	cnt[2] = 3
	cnt[3] = 4
	cnt[4] = 5
	for i in range(5, n):
		tmp = dp[i - 3] + b[i] - b[i - 2]
		cnt[i] = 3
		if i >= 6 and tmp >= dp[i - 4] + b[i] - b[i - 3]:
			tmp = dp[i - 4] + b[i] - b[i - 3]
			cnt[i] = 4
		if i >= 7 and tmp >= dp[i - 5] + b[i] - b[i - 4]:
			tmp = dp[i - 5] + b[i] - b[i - 4]
			cnt[i] = 5
		dp[i] = tmp
	k = 0
	qq = 0
	for i in range(n - 1, -1, -1):
		if k == 0:
			qq += 1
			k = cnt[i] - 1
			cnt[i] = qq
		else:
			cnt[i] = qq
			k -= 1
	idx = [0] * n
	for (i, e) in enumerate(a):
		kk = bisect.bisect_left(b, e)
		idx[i] = cnt[kk]
		b[kk] -= 1
	print(dp[-1], qq)
	for e in idx:
		print(e, end=' ')


import heapq
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split())) + [0]
h = []
for i in range(n):
	heapq.heappush(h, (a[i], i))
b = []
for _ in range(3):
	(ai, i) = heapq.heappop(h)
	b.append(i)
dp = [0] * (n + 1)
dpmin = [0] * n
for i in range(3, n):
	(aj, j) = heapq.heappop(h)
	dp[i] = dpmin[i - 3] + a[b[-1]] - aj
	dpmin[i] = min(dpmin[i - 1], dp[i])
	b.append(j)
dp[n] = dpmin[n - 3] + a[b[-1]]
b.append(n)
res = dp[n] - a[b[0]]
ans = [0] * (n + 1)
i = n
k = 1
while i:
	for j in range(i - 1, i - 3, -1):
		ans[b[j]] = k
	j = i - 3
	while j >= 0:
		if dp[j] + a[b[i - 1]] - a[b[i]] == dp[i] and j >= 3:
			ans[b[j]] = k
			k += 1
			i = j
			break
		ans[b[j]] = k
		j -= 1
	if j < 0:
		break
ans.pop()
print(res, k)
print(*ans)


def solve_ee(ls):
	dp = [float('inf')] * (len(ls) + 1)
	dp[0] = 0
	p = [0] * (len(ls) + 1)
	for i in range(len(ls)):
		for j in range(3, len(ls)):
			if j <= 5 and i + j <= len(ls):
				diff = ls[i + j - 1][0] - ls[i][0]
				if dp[i + j] > dp[i] + diff:
					p[i + j] = i
					dp[i + j] = dp[i] + diff
			else:
				break
	return (dp, p)
n = int(input())
arr = list(map(int, input().split()))
ls = [(v, i) for (i, v) in enumerate(arr)]
ls.sort()
(t, p) = solve_ee(ls)
cur = len(ls)
cnt = 0
team = [0] * 2 * len(ls)
while cur != 0:
	for i in range(cur - 1, p[cur] - 1, -1):
		team[ls[i][1]] = cnt
	cnt += 1
	cur = p[cur]
if len(ls) <= 5:
	print(max(arr) - min(arr), 1)
else:
	print(t[len(ls)], cnt)
for i in range(len(ls)):
	print(team[i] + 1, end=' ')


from operator import itemgetter
from math import inf
n = int(input())
a = list(map(int, input().split()))
s = list(enumerate(a))
s.sort(key=itemgetter(1))
dp = [inf] * (n + 1)
dp[0] = 0
p = [-1] * (n + 1)
for (i, (j, aj)) in enumerate(s):
	for k in range(i - 2, i - 6, -1):
		if k >= 0 and dp[k] + abs(s[i][1] - s[k][1]) < dp[i + 1]:
			dp[i + 1] = dp[k] + abs(s[i][1] - s[k][1])
			p[i + 1] = k
t = [-1] * n
i = n
j = 1
while i:
	k = p[i]
	for l in range(k, i):
		t[s[l][0]] = j
	i = k
	j += 1
print(dp[n], len(set(t)))
print(*t)


n = int(input())
inf = 10 ** 18
a = sorted(((v, i) for (i, v) in enumerate(map(int, input().split())))) + [(inf ** 2, -1)] * 5
dp = [0] + [inf] * (n + 10)
dpi = [-1] * (n + 10)
for i in range(n):
	for j in range(i + 2, i + 5):
		cost = a[j][0] - a[i][0]
		if dp[j + 1] > dp[i] + cost:
			dp[j + 1] = dp[i] + cost
			dpi[j + 1] = i
dest = dpi[n]
g = 1
groups = [0] * n
for i in range(n - 1, -1, -1):
	groups[a[i][1]] = g
	if i == dest:
		dest = dpi[i]
		g += 1
print(dp[n], g - 1)
print(*groups)


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
B = [(a, ind) for (ind, a) in enumerate(A)]
B.sort()
DP = [0] * (n + 1)
for i in range(3, n - 2):
	DP[i] = max(DP[i - 1], DP[i - 3] + B[i][0] - B[i - 1][0])
MAX = max(DP)
x = DP.index(MAX)
REMLIST = []
while x > 0:
	if DP[x] == DP[x - 1]:
		x -= 1
	else:
		REMLIST.append(x)
		x -= 3
REMLIST.sort()
REMLIST.append(1 << 60)
print(max(A) - min(A) - MAX, len(REMLIST))
ANS = [-1] * n
remind = 0
NOW = 1
for i in range(n):
	if i == REMLIST[remind]:
		NOW += 1
		remind += 1
	ANS[B[i][1]] = NOW
print(*ANS)


from math import *
from collections import *
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	a[i] = [a[i], i]
a.sort()
ct = 1
ans = [0 for i in range(n)]
dp = [1e+18 for i in range(n)]
ans[1] = -1
ans[1] = -1
ans[2] = -1
dp[2] = a[2][0] - a[0][0]
dp[3] = a[3][0] - a[0][0]
dp[4] = a[4][0] - a[0][0]
for i in range(5, n):
	if dp[i - 3] + a[i][0] - a[i - 2][0] > dp[i - 4] + a[i][0] - a[i - 3][0]:
		if dp[i - 5] + a[i][0] - a[i - 4][0] > dp[i - 4] + a[i][0] - a[i - 3][0]:
			dp[i] = dp[i - 4] + a[i][0] - a[i - 3][0]
			ans[i] = i - 4
		else:
			dp[i] = dp[i - 5] + a[i][0] - a[i - 4][0]
			ans[i] = i - 5
	elif dp[i - 5] + a[i][0] - a[i - 4][0] > dp[i - 3] + a[i][0] - a[i - 2][0]:
		dp[i] = dp[i - 3] + a[i][0] - a[i - 2][0]
		ans[i] = i - 3
	else:
		dp[i] = dp[i - 5] + a[i][0] - a[i - 4][0]
		ans[i] = i - 5
i = n - 1
while i > 0:
	prev = i
	i = ans[i]
	for j in range(prev, i, -1):
		ans[j] = str(ct)
	ct += 1
ans[0] = str(ct - 1)
print(dp[n - 1], ct - 1)
b = [0 for i in range(n)]
for i in range(n):
	ind = a[i][1]
	b[ind] = ans[i]
print(' '.join(b))


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	n = mint()
	a = [0] * n
	b = [0] * n
	j = 0
	for i in mints():
		a[j] = (i, j)
		j += 1
	a.sort()
	dp = [(2000000005, 0)] * (n + 1)
	dp[3] = (a[2][0] - a[0][0], 3)
	if n > 3:
		dp[4] = (a[3][0] - a[0][0], 4)
	if n > 4:
		dp[5] = (a[4][0] - a[0][0], 5)
	for i in range(6, n + 1):
		dp[i] = min(dp[i], (dp[i - 3][0] + a[i - 1][0] - a[i - 3][0], 3))
		dp[i] = min(dp[i], (dp[i - 4][0] + a[i - 1][0] - a[i - 4][0], 4))
		dp[i] = min(dp[i], (dp[i - 5][0] + a[i - 1][0] - a[i - 5][0], 5))
	m = n
	ans = [0] * n
	z = 0
	while m != 0:
		r = dp[m]
		z += 1
		for i in range(m - r[1], m):
			ans[a[i][1]] = z
		m -= r[1]
	print(dp[n][0], z)
	print(*ans)
solve()


def sort(n, a, b):
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] > a[j]:
				t = a[i]
				a[i] = a[j]
				a[j] = t
				t = pos[i]
				pos[i] = pos[j]
				pos[j] = t
n = int(input())
a = [0] + list(map(int, input().split()))
if n > 1000:
	x = zip(a, list(range(0, n + 1)))
	xs = sorted(x, key=lambda tup: tup[0])
	a = [x[0] for x in xs]
	pos = [x[1] for x in xs]
else:
	pos = list(range(0, n + 1))
	sort(n + 1, a, pos)
w = list(range(0, n + 1))
dp = list(range(0, n + 1))
dp[0] = 0
dp[1] = 10000000000
dp[2] = 10000000000
(w[0], w[1], w[2]) = (0, 0, 0)
for i in range(3, n + 1):
	dp[i] = -1
	w3 = 10000000000
	w4 = 10000000000
	w5 = 10000000000
	if i > 2:
		w3 = dp[i - 3] + a[i] - a[i - 2]
	if i > 3:
		w4 = dp[i - 4] + a[i] - a[i - 3]
	if i > 4:
		w5 = dp[i - 5] + a[i] - a[i - 4]
	dp[i] = min(w3, w4, w5)
	if w3 == dp[i]:
		w[i] = 3
	elif w4 == dp[i]:
		w[i] = 4
	else:
		w[i] = 5
count = 0
i = n
res = list(range(0, n + 1))
while i:
	count += 1
	for j in range(i - w[i] + 1, i + 1):
		res[pos[j]] = count
	i -= w[i]
res.pop(0)
print(dp[n], count)
print(*res, sep=' ')


n = int(input())
aa = list(map(int, input().split()))
a = []
for i in range(n):
	a.append([aa[i], i])
a.sort()
d = []
for i in range(n - 1):
	d.append(a[i + 1][0] - a[i][0])
c = [0 for i in range(n)]
i = 5
while i < n:
	c[i] = max(c[i - 1], c[i - 3] + d[i - 3])
	i += 1
i = n - 1
final = [0 for k in range(n)]
j = 1
while i > 0:
	if c[i] == c[i - 1]:
		i -= 1
	else:
		i -= 3
		final[i] = j
	j += 1
check = [0 for i in range(n)]
count = 1
for i in range(n):
	check[a[i][1]] = count
	if final[i] != 0:
		count += 1
print(a[-1][0] - a[0][0] - c[-1], count)
for i in range(n):
	print(check[i], end=' ')


def main():
	n = int(input())
	a = readIntArr()
	a2 = [[x, i] for (i, x) in enumerate(a)]
	a2.sort(key=lambda x: x[0])
	dp = [inf for _ in range(n)]
	left = [0 for _ in range(n)]
	for i in range(n):
		currSz3 = inf
		currSz4 = inf
		currSz5 = inf
		if i >= 2:
			currSz3 = a2[i][0] - a2[i - 2][0]
		if i >= 3:
			currSz3 += dp[i - 3]
		if i >= 3:
			currSz4 = a2[i][0] - a2[i - 3][0]
		if i >= 4:
			currSz4 += dp[i - 4]
		if i >= 4:
			currSz5 = a2[i][0] - a2[i - 4][0]
		if i >= 5:
			currSz5 += dp[i - 5]
		minn = min(currSz3, currSz4, currSz5)
		if i >= 5:
			if minn == currSz3:
				left[i] = i - 2
			elif minn == currSz4:
				left[i] = i - 3
			else:
				left[i] = i - 4
		dp[i] = minn
	res = dp[n - 1]
	groups = []
	right = n - 1
	while True:
		left_ = left[right]
		temp = []
		for i in range(left_, right + 1):
			temp.append(a2[i][1])
		groups.append(temp)
		if left_ == 0:
			break
		right = left_ - 1
	grouping = [-1 for _ in range(n)]
	for (i, group) in enumerate(groups):
		for student in group:
			grouping[student] = i + 1
	print('{} {}'.format(res, len(groups)))
	oneLineArrayPrint(grouping)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


n = int(input())
x = list(map(int, input().split()))
y = []
for i in range(n):
	y.append(x[i])
m = {}
inf = 885627645626577863562
for i in range(n):
	m[x[i]] = i
x.sort()
(dp, cnt, ans) = ([0] * n, [0] * n, [[] for i in range(n)])
dp[0] = dp[1] = inf
for i in range(2, n):
	dp[i] = inf
	for i2 in range(3, 6):
		if i - i2 == -1:
			if dp[i] > x[i] - x[i - i2 + 1]:
				dp[i] = x[i] - x[i - i2 + 1]
				cnt[i] = i2
		elif i - i2 >= 0:
			if dp[i] > dp[i - i2] + x[i] - x[i - i2 + 1]:
				dp[i] = dp[i - i2] + x[i] - x[i - i2 + 1]
				cnt[i] = i2
(skip, temp) = (inf, 0)
for i in range(n - 1, -1, -1):
	if i <= skip:
		skip = i - cnt[i]
		temp += 1
	if i > skip:
		ans[m[x[i]]].append(temp)
print(dp[n - 1], temp)
for i in range(n):
	p = m[y[i]]
	print(ans[p][len(ans[p]) - 1], end=' ')
	ans[p].pop()


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = [[a[i], i] for i in range(n)]
b.sort()
dp = [0] * (n + 1)
for i in range(3, n - 2):
	dp[i] = max(dp[i - 1], dp[i - 3] + b[i][0] - b[i - 1][0])
MAX = max(dp)
x = dp.index(MAX)
rem_list = []
while x > 0:
	if dp[x] == dp[x - 1]:
		x -= 1
	else:
		rem_list.append(x)
		x -= 3
rem_list.sort()
rem_list.append(1 << 60)
print(max(a) - min(a) - MAX, len(rem_list))
ans = [-1] * n
r = 0
now = 1
for i in range(n):
	if i == rem_list[r]:
		now += 1
		r += 1
	ans[b[i][1]] = now
print(*ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, ls) = (ii(), sorted([(x, i) for (i, x) in enumerate(kk())]))
dp1 = [10000000000] * n
dp2 = [10000000000] * n
dp3m = [10000000000] * n
dp1[0] = 0
for i in range(1, n):
	diff = ls[i][0] - ls[i - 1][0]
	dp1[i] = dp3m[i - 1]
	dp2[i] = dp1[i - 1] + diff
	dp3m[i] = min(dp3m[i - 1], dp2[i - 1]) + diff
c = 3
tm = 1
ans = [0] * n
for i in range(n - 1, 0, -1):
	ans[ls[i][1]] = tm
	if c == 3:
		if dp2[i - 1] + (ls[i][0] - ls[i - 1][0]) == dp3m[i]:
			c = 2
	elif c == 2:
		c = 1
	else:
		c = 3
		tm += 1
ans[ls[0][1]] = tm
print(dp3m[n - 1], tm)
print(*ans)


n = int(input())
pre = [0] * (n + 1)
dp = [10 ** 9] * (n + 1)
oa = [0] + list(map(int, input().split()))
a = sorted(oa)
ai = {}
for i in range(1, n + 1):
	ai.setdefault(oa[i], []).append(i)
mapping = {}
for i in range(1, n + 1):
	mapping[i] = ai[a[i]].pop()
dp[0] = 0
for i in range(3, n + 1):
	for j in range(3, min(6, i + 1)):
		newval = a[i] - a[i - j + 1] + dp[i - j]
		if newval < dp[i]:
			dp[i] = newval
			pre[i] = j
ans = [0] * (n + 1)
cur = n
teami = 1
while cur:
	for i in range(pre[cur]):
		ans[mapping[cur - i]] = teami
	teami += 1
	cur -= pre[cur]
print(dp[n], teami - 1)
print(*ans[1:])


n = int(input())
l = list(map(int, input().split()))
a = [[l[i], i] for i in range(n)]
a.sort()
ll = l.copy()
ll.sort()
if n < 6:
	print(a[-1][0] - a[0][0], 1)
	print(*[1] * n)
else:
	b = [ll[i] - ll[i - 1] for i in range(3, n - 2)]
	dp = [[0, 0] for i in range(len(b) + 5)]
	i = len(b) - 1
	dp[i] = [0, b[i]]
	while i >= 0:
		dp[i][0] = max(dp[i + 1])
		dp[i][1] = max(dp[i + 3]) + b[i]
		i -= 1
	odp = []
	i = 0
	while True:
		if dp[i] == [0, 0]:
			break
		if dp[i][1] > dp[i][0]:
			odp.append(i)
			i += 3
		else:
			i += 1
	odp = [i + 3 for i in odp]
	grupy = [0] * n
	grupa = 1
	wsk = 0
	for i in range(n):
		if wsk <= len(odp) - 1:
			if i == odp[wsk]:
				wsk += 1
				grupa += 1
		grupy[a[i][1]] = grupa
	print(ll[-1] - ll[0] - max(dp[0]), grupa)
	print(*grupy)


from math import inf
I = input
SS = sorted
n = int(I())
A = list(map(int, I().split()))
A = ([index, int(x), -1] for (index, x) in enumerate(A))
A = SS(A, key=lambda tup: tup[1])
dp = [inf] * (n + 1)
dp[0] = 0
p = [-1] * (n + 1)
for i in range(n):
	j = 3
	while j <= 5 and i + j <= n:
		deff = dp[i] + A[i + j - 1][1] - A[i][1]
		dp[i + j] = min(dp[i + j], deff)
		if dp[i + j] == deff:
			p[i + j] = i
		j += 1
ind = n
team = 1
while ind != 0:
	for i in range(ind - 1, p[ind] - 1, -1):
		A[i][2] = team
	team += 1
	ind = p[ind]
print(f'{dp[-1]} {team - 1}')
A = SS(A)
print(*(x for (_, _, x) in A))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = 0
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][0] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
n = int(input())
a = list(map(int, input().split()))
if n < 6:
	print(max(a) - min(a), 1)
	b = [1] * n
	print(*b)
	sys.exit(0)
dp = [[0, 0, 0, 0, 0] for i in range(n)]
for i in range(n):
	dp[i][0] = a[i]
	dp[i][1] = i
dp.sort()
res = [0] * n
(dp[2][2], dp[2][3], dp[2][4]) = (1, 3, dp[2][0] - dp[0][0])
(dp[3][2], dp[3][3], dp[3][4]) = (1, 4, dp[3][0] - dp[0][0])
(dp[4][2], dp[4][3], dp[4][4]) = (1, 5, dp[4][0] - dp[0][0])
for i in range(5, n):
	(dp[i][2], dp[i][3], dp[i][4]) = (1 + dp[i - 3][2], 3, dp[i][0] - dp[i - 2][0] + dp[i - 3][4])
	if i > 5:
		c = dp[i][0] - dp[i - 3][0] + dp[i - 4][4]
		if c < dp[i][4]:
			(dp[i][2], dp[i][3], dp[i][4]) = (1 + dp[i - 4][2], 4, c)
	if i > 6:
		c = dp[i][0] - dp[i - 4][0] + dp[i - 5][4]
		if c < dp[i][4]:
			(dp[i][2], dp[i][3], dp[i][4]) = (1 + dp[i - 5][2], 5, c)
ans = dp[-1][-1]
k = dp[-1][2]
print(ans, k)
i = n - 1
while i >= 0:
	c = dp[i][3]
	for j in range(c):
		res[dp[i][1]] = k
		i -= 1
	k -= 1
print(*res)


n = int(input())
a = list(map(int, input().split()))
idx = sorted(range(n), key=lambda i: a[i])
a = sorted(a)
diff = [x - y for (x, y) in zip(a[1:], a[:-1])]
dp = [0] * (n - 1)
mask = [0] * (n - 1)
for i in range(n - 1):
	if i < 2:
		continue
	if i <= n - 4:
		add = 0 if i == 2 else dp[i - 3]
		if diff[i] + add > dp[i - 1]:
			dp[i] = diff[i] + add
			mask[i] = 1
		else:
			dp[i] = dp[i - 1]
	else:
		dp[i] = dp[i - 1]
i = n - 2
while i >= 0:
	if mask[i] == 1:
		for _ in range(2):
			i -= 1
			if i >= 0:
				mask[i] = 0
	i -= 1
comp = [None] * n
cur = 1
comp[0] = cur
for (i, x) in enumerate(mask):
	if x == 1:
		cur += 1
		comp[i + 1] = cur
	else:
		comp[i + 1] = comp[i]
ans = [None] * n
for (i, x) in enumerate(idx):
	ans[x] = str(comp[i])
print(str(sum(diff) - dp[-1]) + ' ' + str(cur))
print(' '.join(ans))


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = list(map(lambda xx: [int(xx), 0], input().split()))
	for i in range(n):
		a[i][1] = i
	a.sort(key=lambda xx: xx[0], reverse=1)
	dp = [[10 ** 18 for _ in range(3)] for _ in range(n)]
	dp[0][0] = a[0][0]
	for i in range(1, n):
		dp[i][0] = dp[i - 1][2] - a[i - 1][0] + a[i][0]
		dp[i][1] = dp[i - 1][0]
		dp[i][2] = min(dp[i - 1][1], dp[i - 1][2])
	(tran, ls) = ([n - 1], 2)
	for i in range(n - 2, -1, -1):
		if ls == 2 and dp[i][2] > dp[i][1]:
			ls = 1
		elif ls == 1:
			ls = 0
		elif not ls:
			tran.append(i)
			ls = 2
	tran.append(-1)
	tran.reverse()
	ans = [0] * n
	for i in range(len(tran) - 1):
		for j in range(tran[i] + 1, tran[i + 1] + 1):
			ans[a[j][1]] = i + 1
	print(dp[n - 1][2] - a[n - 1][0], len(tran) - 1)
	print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
from sys import stdin
n = int(stdin.readline())
ao = list(map(int, stdin.readline().split()))
ai = [(ao[i], i) for i in range(n)]
ai.sort()
a = [ai[i][0] for i in range(n)]
dp = [[float('inf')] * 3 for i in range(n + 1)]
pp = [[0, 1, 2] for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
	if dp[i + 1][1] > dp[i][0] - a[i]:
		dp[i + 1][1] = dp[i][0] - a[i]
		pp[i + 1][1] = 0
	if dp[i + 1][2] > dp[i][1]:
		dp[i + 1][2] = dp[i][1]
		pp[i + 1][2] = 1
	if dp[i + 1][2] > dp[i][2]:
		dp[i + 1][2] = dp[i][2]
		pp[i + 1][2] = 2
	if dp[i + 1][0] > dp[i][2] + a[i]:
		dp[i + 1][0] = dp[i][2] + a[i]
		pp[i + 1][0] = 2
ansmax = dp[n][0]
ans = [None] * n
now = 1
nv = pp[n][0]
for i in range(n - 1, -1, -1):
	ans[ai[i][1]] = now
	if nv == 0:
		now += 1
	nv = pp[i][nv]
print(ansmax, max(ans))
print(*ans)


n = int(input())
a = sorted(((int(v), i) for (i, v) in enumerate(input().split())))
INF = 10 ** 18
dp = [-INF, -INF, 0]
for i in range(n - 1):
	dp.append(max(dp[-1], dp[i] + a[i + 1][0] - a[i][0]))
(cur, t) = (n - 1, 1)
o = [0] * n
while cur >= 0:
	if dp[cur] == dp[cur - 1]:
		o[a[cur][1]] = t
		cur -= 1
	else:
		o[a[cur][1]] = o[a[cur - 1][1]] = o[a[cur - 2][1]] = t
		cur -= 3
		t += 1
print(a[-1][0] - a[0][0] - dp[n - 1], t - 1)
print(*o)


n = int(input().strip())
order = dict()
nums = [(int(i), index) for (index, i) in enumerate(input().strip().split())]
nums.sort()
order = [i[1] for i in nums]
nums = [i[0] for i in nums]
dp = [100000010000 for i in range(n + 1)]
dp[0] = 0
p = [-1 for i in range(n + 1)]
for i in range(n + 1):
	for j in range(3, 6):
		if i + j <= n:
			diff = nums[i + j - 1] - nums[i]
			if dp[i + j] > dp[i] + diff:
				p[i + j] = i
				dp[i + j] = dp[i] + diff
cur = n
cnt = 0
ans = dict()
while cur != 0:
	for i in range(cur - 1, p[cur] - 1, -1):
		ans[order[i]] = cnt
	cnt += 1
	cur = p[cur]
print(dp[n], ans[order[0]] + 1)
for i in range(n):
	print(ans[i] + 1, end=' ')
print()


n = int(input())
arr = sorted(((v, i) for (i, v) in enumerate(map(int, input().split(' ')))))
ans = [0] * n
if n == 3:
	print(arr[2][0] - arr[0][0], 1)
	for i in n:
		ans[i] = i
elif n == 4:
	print(arr[3][0] - arr[0][0], 1)
	for i in n:
		ans[i] = i
else:
	INF = 1000000000000000000
	dp = [0, INF, INF, arr[2][0] - arr[0][0], arr[3][0] - arr[0][0]]
	for i in range(4, n):
		dp.append(min(dp[i - 2] + arr[i][0] - arr[i - 2][0], dp[i - 3] + arr[i][0] - arr[i - 3][0], dp[i - 4] + arr[i][0] - arr[i - 4][0]))
	(cnt, ls) = (1, n)
	for i in range(n, 0, -1):
		ans[arr[i - 1][1]] = cnt
		if dp[i - 1] + arr[ls - 1][0] - arr[i - 1][0] == dp[ls] and ls - i > 1:
			ls = i - 1
			cnt += 1
	print(dp[n], cnt - 1)
print(*ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect
n = int(input())
a = [int(s) for s in input().split()]
inc = list(range(n))
inc.sort(key=lambda i: a[i])
A = [a[i] for i in inc]
cliff = [0] * n
for i in range(1, n):
	cliff[i] = A[i] - A[i - 1]
total = A[n - 1] - A[0]
memoSum = collections.deque([-1, -1, 0, -1, -1])
cliff.append(0)
steps = [0] * (n + 1)
for i in range(3, n + 1):
	choice = max(0, 1, 2, key=lambda i: memoSum[i])
	steps[i] = 5 - choice
	memoSum.append(memoSum[choice] + cliff[i])
	memoSum.popleft()
diversity = total - memoSum[-1]
ans = [0] * n
i = n
teamTag = 0
while i > 0:
	teamTag += 1
	teamMem = steps[i]
	for j in range(teamMem):
		i -= 1
		ans[inc[i]] = teamTag
print('{} {}'.format(diversity, teamTag))
print(' '.join((str(i) for i in ans)))


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 30, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += 1
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += 1
		self.temp.data = pre_xor

	def query(self, xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = xor & 1 << i
			if not val:
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				elif self.temp.right:
					self.temp = self.temp.right
			elif self.temp.right and self.temp.right.count > 0:
				self.temp = self.temp.right
			elif self.temp.left:
				self.temp = self.temp.left
			self.temp.count -= 1
		return xor ^ self.temp.data
n = int(input())
l = list(map(int, input().split()))
ind = [i for i in range(n)]
dp = [0 for i in range(n + 1)]
ind = sort_list(ind, l)
l.sort()
if n <= 4:
	print(l[-1], l[0], 1)
	print(*[1] * n)
	sys.exit(0)
ide = [i for i in range(n)]
for i in range(5):
	dp[i] = l[i] - l[0]
	ide[i] = -1
for i in range(5, n):
	dp[i] = dp[i - 3] + l[i] - l[i - 2]
	t = i
	ide[t] = t - 3
	if i > 5 and dp[i] > dp[i - 4] + l[i] - l[i - 3]:
		dp[i] = dp[i - 4] + l[i] - l[i - 3]
		ide[t] = t - 4
	if i > 6 and dp[i] > dp[i - 5] + l[i] - l[i - 4]:
		dp[i] = dp[i - 5] + l[i] - l[i - 4]
		ide[t] = t - 5
	if i > 7 and dp[i] > dp[i - 6] + l[i] - l[i - 5]:
		dp[i] = dp[i - 6] + l[i] - l[i - 5]
		ide[t] = t - 6
cou = 1
k = n - 1
tot = []
while k > 0:
	for i in range(ide[k], k):
		tot.append(cou)
	cou += 1
	k = ide[k]
tot = tot[::-1]
print(dp[n - 1], max(tot))
tot = sort_list(tot, ind)
print(*tot)


import sys
from copy import *
from bisect import *
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
uu = t
while t > 0:
	t -= 1
	n = fi()
	a = li()
	b = deepcopy(a)
	a.sort()
	d = {}
	for i in range(n):
		if b[i] not in d:
			d[b[i]] = []
		d[b[i]].append(i)
	p = []
	for i in range(1, n):
		p.append(a[i] - a[i - 1])
	dp = [0] * len(p)
	for i in range(2, len(p)):
		if i <= 4:
			dp[i] = max(dp[i - 1], p[i])
		else:
			dp[i] = max(dp[i - 1], p[i] + dp[i - 3])
		if n - i <= 3:
			dp[i] = dp[i - 1]
	c = 1
	j = n - 2
	ans = [0] * n
	ans[d[a[n - 1]][-1]] = 1
	d[a[n - 1]].pop()
	cur = dp[-1]
	cur = bisect_left(dp, dp[-1])
	while j >= 1:
		if j == cur:
			cur = bisect_left(dp, dp[j] - p[j])
			c += 1
		ans[d[a[j]][-1]] = c
		d[a[j]].pop()
		j -= 1
	ans[d[a[0]][-1]] = c
	print(sum(p) - dp[-1], c)
	print(*ans)