A permutation is a sequence of integers from 1 to n of length n containing each number exactly once. For example, (1), (4, 3, 5, 1, 2), (3, 2, 1) are permutations, and (1, 1), (4, 3, 1), (2, 3, 4) are not. 

There are many tasks on permutations. Today you are going to solve one of them. Let’s imagine that somebody took several permutations (perhaps, with a different number of elements), wrote them down consecutively as one array and then shuffled the resulting array. The task is to restore the initial permutations if it is possible.

Input

The first line contains an integer n (1 ≤ n ≤ 105). The next line contains the mixed array of n integers, divided with a single space. The numbers in the array are from 1 to 105.

Output

If this array can be split into several permutations so that every element of the array belongs to exactly one permutation, print in the first line the number of permutations. The second line should contain n numbers, corresponding to the elements of the given array. If the i-th element belongs to the first permutation, the i-th number should be 1, if it belongs to the second one, then its number should be 2 and so on. The order of the permutations’ numbering is free.

If several solutions are possible, print any one of them. If there’s no solution, print in the first line  - 1.

Examples

Input

9
1 2 3 1 2 1 4 2 5


Output

3
3 1 2 1 2 2 2 3 2


Input

4
4 3 2 1


Output

1
1 1 1 1 

Input

4
1 2 2 3


Output

-1

Note

In the first sample test the array is split into three permutations: (2, 1), (3, 2, 1, 4, 5), (1, 2). The first permutation is formed by the second and the fourth elements of the array, the second one — by the third, the fifth, the sixth, the seventh and the ninth elements, the third one — by the first and the eigth elements. Clearly, there are other splitting variants possible.

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
def fail():
	print(-1)
	import sys
	sys.exit()
n = int(input())
count = (n + 1) * [0]
assign = n * [None]
for (i, x) in enumerate(map(int, input().split())):
	if x > n:
		fail()
	count[x] += 1
	assign[i] = count[x]
for i in range(2, n):
	if count[i - 1] < count[i]:
		fail()
print(count[1])
print(' '.join(map(str, assign)))


n = int(input())
l = [int(i) for i in input().split()]
from collections import Counter
c = Counter(l)
prev = c[1]
cnt = c[1]
f = 1
from collections import defaultdict
d = defaultdict(list)
for i in range(n):
	d[l[i]].append(i)
for i in range(2, max(l) + 1):
	if c[i] > prev:
		f = 0
		break
	prev = c[i]
if not f:
	print(-1)
	exit()
l = [[] for i in range(10 ** 5 + 3)]
for i in range(n, 0, -1):
	if c[i] > 0:
		for j in range(c[i]):
			l[j].append(d[i].pop())
print(cnt)
ans = [0] * n
for i in range(len(l)):
	for j in range(len(l[i])):
		ans[l[i][j]] = i + 1
print(*ans)


n = int(input())
lst = [*map(int, input().split())]
(d, di) = ({}, {})
for (i, x) in enumerate(lst):
	if d.get(x) == None:
		d[x] = []
		di[x] = 0
	d[x].append(i)
	di[x] += 1
lst = [*set(lst)]
lst.sort()
from sys import exit
if d.get(1) == None:
	print(-1)
	exit()
res = [0] * n
for (i, x) in enumerate(d[1]):
	res[x] = i + 1
for (i, x) in enumerate(lst[1:]):
	if x - lst[i] == 1:
		if di[x] <= di[lst[i]]:
			for (j, y) in enumerate(d[x]):
				res[y] = j + 1
		else:
			print(-1)
			exit()
	else:
		print(-1)
		exit()
print(di[1])
print(*res)


n = int(input())
arr = list(map(int, input().split()))
res = [0] * n
mx = 0
l = [0] * 100001
for i in range(n):
	l[arr[i]] += 1
	mx = max(mx, arr[i])
for i in range(1, mx):
	if l[i + 1] > l[i]:
		print(-1)
		break
else:
	copy = l[:]
	print(l[1])
	for i in range(n):
		l[arr[i]] -= 1
		res[i] = copy[arr[i]] - l[arr[i]]
	print(' '.join(list(map(str, res))))


n = int(input())
t = list(map(int, input().split()))
(l, m) = (min(t), max(t))
if l < 1 or m > n:
	print(-1)
else:
	(r, p) = ([0] * (m + 1), [0] * n)
	for (i, j) in enumerate(t):
		r[j] += 1
		p[i] = r[j]
	if any((r[j + 1] > r[j] for j in range(1, m))):
		print(-1)
	else:
		print(r[1])
		print(' '.join(map(str, p)))


n = int(input())
a = list(map(int, input().split()))
count = [0] * 100005
mx = 0
for i in range(n):
	count[a[i]] += 1
	mx = max(mx, count[a[i]])
	a[i] = count[a[i]]
ans = True
for i in range(1, 100004):
	if count[i] < count[i + 1]:
		ans = False
		break
if ans:
	print(mx)
	print(*a)
else:
	print(-1)


from collections import Counter

def main():
	n = int(input())
	numbers = list(map(int, input().split()))
	permutations = []
	cnt = Counter()
	for number in numbers:
		cnt[number] += 1
		permutations.append(cnt[number])
	if cnt[1] == 0:
		return '-1'
	(buff_k, buff_d) = (0, 0)
	for (d, k) in sorted(cnt.items()):
		if (k <= buff_k or buff_k == 0) and (d == buff_d + 1 or buff_d == 0):
			(buff_k, buff_d) = (k, d)
		else:
			return '-1'
	return ''.join([str(cnt[1]), '\n', ' '.join(list(map(str, permutations)))])
print(main())


import sys
n = int(input())
arr = [int(x) for x in input().split()]
kk = max(arr)
a2 = []
for i in range(kk + 1):
	a2.append(0)
for i in range(n):
	a2[arr[i]] += 1
for i in range(2, len(a2)):
	if a2[i] > a2[i - 1]:
		print(-1)
		sys.exit()
print(a2[1])
for i in range(n):
	print(a2[arr[i]], end=' ')
	a2[arr[i]] -= 1


from collections import Counter
n = int(input())
l = list(map(int, input().split()))
ans = [0] * (max(l) + 1)
for i in l:
	ans[i] += 1
mn = ans[1]
for x in range(1, len(ans)):
	if ans[x] > mn:
		print(-1)
		exit()
	else:
		mn = ans[x]
print(ans[1])
for y in l:
	print(ans[y], end=' ')
	ans[y] -= 1


n = int(input())
a = []
mx = -1
for x in input().split():
	a.append(int(x))
	mx = max(mx, int(x))
b = [0 for x in range(mx + 1)]
for x in a:
	b[x] += 1
ck = True
for i in range(1, mx):
	if b[i + 1] > b[i]:
		ck = False
		break
if ck:
	c = [1 for x in range(mx + 1)]
	ans = []
	for x in a:
		ans.append(c[x])
		c[x] += 1
	print(max(c) - 1)
	print(*ans)
else:
	print(-1)


n = int(input())
a = [int(x) for x in input().split()]
ss = [0] * (n + 1)
flag = 1
for i in range(n):
	if a[i] <= 0 or a[i] > n:
		flag = 0
		break
	ss[a[i]] += 1
if flag:
	for i in range(1, n):
		if ss[i] < ss[i + 1]:
			flag = 0
			break
if flag:
	print(ss[1])
	for i in a:
		print(ss[i], end=' ')
		ss[i] -= 1
	print()
else:
	print(-1)


import sys
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
l = [0] * 10 ** 5
for i in range(n):
	l[a[i] - 1] += 1
flag = True
for i in range(1, len(l)):
	if l[i] > l[i - 1]:
		print(-1)
		flag = False
		break
if flag:
	arr = [0] * (10 ** 5 + 1)
	ans = [0] * n
	for i in range(n):
		ans[i] = arr[a[i]] + 1
		arr[a[i]] += 1
	print(max(ans))
	print(*ans)


n = int(input())
a = list(map(int, input().split()))
count = [0] * 10 ** 6
f = 1
m = max(a)
for i in range(n):
	count[a[i]] += 1
for i in range(2, n + 1):
	if count[i] > count[i - 1]:
		f = 0
		break
for i in range(2, m + 1):
	if count[i] == 0 or count[i] > count[i - 1]:
		f = 0
		break
if count[1] == 0:
	f = 0
if f == 0:
	print(-1)
else:
	f = [0] * 10 ** 6
	ans = []
	for i in range(n):
		ans.append(f[a[i]] + 1)
		f[a[i]] += 1
	print(count[1])
	print(*ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
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')
n = int(input())
a = list(map(int, input().split()))
me = max(a)
d = dict()
for i in a:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
ch = 1
for i in range(me - 1, 0, -1):
	if i not in d or i + 1 not in d or d[i] < d[i + 1]:
		ch = 0
		break
if ch == 0:
	print(-1)
else:
	prev = 0
	count = 0
	r = [1] * (me + 1)
	for i in range(me, 0, -1):
		ct = d[i] - prev
		count += ct
		prev = d[i]
	b = list()
	for i in a:
		b.append(r[i])
		r[i] += 1
	print(count)
	print(*b)


from collections import OrderedDict
n = int(input())
arr = list(map(int, input().split()))
pos_dict = OrderedDict()
for i in range(len(arr)):
	curr = arr[i]
	if curr in pos_dict:
		temp = pos_dict[curr]
		pos_dict[curr].append(i)
	else:
		pos_dict[curr] = [i]
i_list = sorted(pos_dict, reverse=True)
pos_list = [-1 for i in range(len(arr))]
group_no = 0
k = 0
while k < len(i_list):
	x = i_list[k]
	if len(pos_dict[x]) > 0:
		group_no += 1
		for curr in range(x, 0, -1):
			if curr not in pos_dict or len(pos_dict[curr]) == 0:
				print(-1)
				exit()
			else:
				index = pos_dict[curr].pop()
				pos_list[index] = group_no
	else:
		k += 1
print(group_no)
for x in pos_list:
	print(x, end=' ')


n = int(input())
l = list(map(int, input().split()))
dic = {}
li = list(set(l))
a = len(li)
b = max(li)
if b > a:
	print(-1)
else:
	for i in range(a):
		dic[i + 1] = 0
	for i in range(n):
		dic[l[i]] += 1
	ls = []
	for i in range(a):
		s = [i + 1, dic[i + 1]]
		ls.append(s)
	jud = 0
	for i in range(1, a):
		if ls[i][1] > ls[i - 1][1]:
			print(-1)
			jud = 1
			break
	if jud == 0:
		print(dic[1])
		lt = []
		for i in range(n):
			ss = dic[l[i]]
			dic[l[i]] -= 1
			lt.append(str(ss))
		print(' '.join(lt))


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')
from collections import Counter
import heapq
from collections import Counter
from bisect import bisect_right
n = int(input())
arr = [(int(x), i) for (i, x) in enumerate(input().split())]
arr.sort(key=lambda x: x[0])
var = 1
ans = [0] * n
ans[arr[0][1]] = 1
f = 0
mxx = 1
cnt = 1
ma = 10 ** 5
if arr[0][0] != 1:
	print(-1)
	exit()
for i in range(1, n):
	cnt += 1
	if arr[i][0] == arr[i - 1][0]:
		ans[arr[i][1]] = var + 1
		var += 1
		mxx = max(var, mxx)
		cnt += 1
		if cnt > ma:
			f = 1
			break
	else:
		if int(arr[i][0]) != int(arr[i - 1][0]) + 1:
			f = 1
			break
		var = 1
		ans[arr[i][1]] = var
		mxx = max(var, mxx)
		ma = cnt
		cnt = 1
if f == 1 or (n == 1 and arr[0][0] != 1):
	print(-1)
else:
	print(mxx)
	print(*ans)


n = int(input())
cnt = [set() for i in range(10 ** 5 + 1)]
a = list(map(int, input().split()))
for i in range(n):
	cnt[a[i] - 1].add(i)
res = [0] * n
ends = []
for i in range(len(cnt) - 1):
	if len(cnt[i + 1]) - len(cnt[i]) > 0:
		print(-1)
		exit()
	ends.append((i + 1, -len(cnt[i + 1]) + len(cnt[i])))
if len(cnt[-1]) > 0:
	ends.append((10 ** 5, len(cnt[-1])))
new_cnt = 0
for i in ends:
	for j in range(i[1]):
		new_cnt += 1
		cur = []
		for k in range(i[0]):
			res[cnt[k].pop()] = new_cnt
print(new_cnt)
print(' '.join(map(str, res)))


def solve():
	_ = input()
	arr = list(map(int, input().split()))
	frq = {k: 0 for k in range(1, 100001)}
	inds = {k: 1 for k in range(1, 100001)}
	for v in arr:
		frq[v] += 1
	for i in range(1, len(frq)):
		if frq[i] < frq[i + 1]:
			print(-1)
			return
	print(frq[1])
	for v in arr:
		print(inds[v], end=' ')
		inds[v] += 1
solve()