Valera has 2·n cubes, each cube contains an integer from 10 to 99. He arbitrarily chooses n cubes and puts them in the first heap. The remaining cubes form the second heap. 

Valera decided to play with cubes. During the game he takes a cube from the first heap and writes down the number it has. Then he takes a cube from the second heap and write out its two digits near two digits he had written (to the right of them). In the end he obtained a single fourdigit integer — the first two digits of it is written on the cube from the first heap, and the second two digits of it is written on the second cube from the second heap.

Valera knows arithmetic very well. So, he can easily count the number of distinct fourdigit numbers he can get in the game. The other question is: how to split cubes into two heaps so that this number (the number of distinct fourdigit integers Valera can get) will be as large as possible?


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100). The second line contains 2·n space-separated integers a_{i} (10 ≤ a_{i} ≤ 99), denoting the numbers on the cubes.


-----Output-----

In the first line print a single number — the maximum possible number of distinct four-digit numbers Valera can obtain. In the second line print 2·n numbers b_{i} (1 ≤ b_{i} ≤ 2). The numbers mean: the i-th cube belongs to the b_{i}-th heap in your division.

If there are multiple optimal ways to split the cubes into the heaps, print any of them.


-----Examples-----
Input
1
10 99

Output
1
2 1 

Input
2
13 24 13 45

Output
4
1 2 2 1 



-----Note-----

In the first test case Valera can put the first cube in the first heap, and second cube — in second heap. In this case he obtain number 1099. If he put the second cube in the first heap, and the first cube in the second heap, then he can obtain number 9910. In both cases the maximum number of distinct integers is equal to one.

In the second test case Valera can obtain numbers 1313, 1345, 2413, 2445. Note, that if he put the first and the third cubes in the first heap, he can obtain only two numbers 1324 and 1345.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
g = [[] for i in range(100)]
for i in range(2 * n):
    g[a[i]].append(i)
x = [0, 0]
cur = 1
mus = []
ans = [0] * 2 * n
for i in range(10, 100):
    if len(g[i]) == 1:
        ans[g[i][0]] = cur
        x[cur - 1] += 1
        cur = 3 - cur
    if len(g[i]) >= 2:
        ans[g[i][0]] = 1
        ans[g[i][1]] = 2
        x[0] += 1
        x[1] += 1
        for j in range(2, len(g[i])):
            mus.append(g[i][j])
for i in range(len(mus)):
    ans[mus[i]] = 2 - (i % 2)
print(x[0] * x[1])
print(*ans)
        


n = int(input())
a = list(map(int, input().split()))
proc = sorted([ (a.count(i), i) for i in range(10, 100) if a.count(i) > 0 ])
left, right = [], []
for cnt, val in proc:
    half = cnt // 2
    left.extend([val] * half)
    right.extend([val] * half)
    if cnt % 2 == 1:
        if len(left) < len(right):
            left.append(val)
        else:
            right.append(val)
print(len(set(left)) * len(set(right)))
cnt = [0 for i in range(100)]
for i in range(2 * n):
    if left.count(a[i]) == cnt[a[i]]:
        print('2', end = ' ')
    else:
        print('1', end = ' ')
        cnt[a[i]] += 1


N = int(input())
Nums = list(map(int, input().split()))
Good = [1] * (N * 2)
Amounts = [0] * 100
Mono, Duo = 0, 0
for Num in Nums:
    if Amounts[Num] == 0:
        Mono += 1
    elif Amounts[Num] == 1:
        Duo += 1
        Mono -= 1
    Amounts[Num] += 1
Flag = Mono % 2
Duo_Flag = False
Counts = [0] * 100
for i in range(2 * N):
    Num = Nums[i]
    if Amounts[Num] == 1:
        if Flag:
            Good[i] = 1
        else:
            Good[i] = 2
        Flag = not Flag
    else:
        if Counts[Num] == 0:
            Good[i] = 1
        elif Counts[Num] == 1:
            Good[i] = 2
        else:
            if Duo_Flag:
                Good[i] = 1
            else:
                Good[i] = 2
            Duo_Flag = not Duo_Flag
        Counts[Num] += 1
print((Duo + (Mono // 2)) * (Duo + ((Mono + 1) // 2)))
print(*Good)


from math import*
from random import*

n = int(input()) * 2
A = list(map(int, input().split()))
amount = [0] * 101

B = []
for i in range(n):
    if amount[A[i]] < 2:
        amount[A[i]] += 1
        B += [(A[i], i)]
B.sort()
x, y = [], []
for i in range(len(B)):
    if(i % 2 == 0):
        x.append(B[i][1])
    else:
        y.append(B[i][1])
lolka = 0
aaa = 0
# print(x)
# print(y)
print(len(x) * len(y))
for i in range(n):
    if i in x:
        lolka += 1
        aaa += 1
        print(1, end = ' ')
    elif i in y:
        print(2, end = ' ')
    else:
        if len(x) - lolka + aaa < n // 2:
            print(1, end = ' ')
            aaa += 1
        else:
            print(2, end = ' ')
print()

# B, C = [], []
# for i in range(n):


# S = list(set(A))
# where = [0] * 101
# am1, am2 = 0, 0
# for i in range(len(S)):
#     if(i % 2 == 0):
#         where[S[i]] = 1
#         am1 += 1
#     else:
#         where[S[i]] = 2
#         am2 += 1
# used = [0] * 201
# for i in range(n):
#     if not used[A[i]]:
#         print(where[A[i]])
#         used[A[i]] = True
#     else:
#         print(3 - where[A[i]])

n = int(input())
a = list(map(int, input().split()))
R = range(100)
c = [[] for _ in [0]*100]
for i in range(n*2):
	c[a[i]].append(i)
d = [0]*200
heap = 1
z = [0, 0, 0]
for i in R:
	if len(c[i]) == 1:
		z[heap]+=1
		d[c[i][0]] = heap
		heap = 3 - heap;
for i in R:
	if len(c[i]) > 1:
		z[1]+=1
		z[2]+=1
		while len(c[i]):
			d[c[i].pop()] = heap
			heap = 3 - heap

print(z[1]*z[2])
print(' '.join(map(str, d[:n*2])))

n = int(input())
a = list(map(int, input().split()))
R = range(100)
c = [[] for i in range(100)]
for i in range(n*2):
	c[a[i]].append(i)
d = [0]*200
heap = 1
z = [0, 0, 0]
for i in R:
	if len(c[i]) == 1:
		z[heap]+=1
		d[c[i][0]] = heap
		heap = 3 - heap;
for i in R:
	if len(c[i]) > 1:
		z[1]+=1
		z[2]+=1
		while len(c[i]):
			d[c[i].pop()] = heap
			heap = 3 - heap

print(z[1]*z[2])
print(' '.join(map(str, d[:n*2])))

n, t = 2 * int(input()), map(int, input().split())
d = [[] for i in range(100)]
for i, j in enumerate(t):
    d[j].append(i)
y, x = [], False
p, q = [], ['1'] * n
for i in d[10: 100]:
    if i:
        if len(i) == 1:
            if x: y.append(i[0])
            x = not x
        else:
            y.append(i[0])
            p += i[2: ]
k, l = len(p), len(y)
print(l * (n - k - l))
for i in y:
    q[i] = '2'
for i in (p[k // 2: ] if x else p[: k // 2]):
    q[i] = '2'
print(' '.join(q))

#!/usr/bin/env python3
n = int(input())
a = list(map(int,input().split()))
c = [0] * 100
for i in a:
    c[i] += 1
x = [0] * 100
y = [0] * 100
j = 0
for i in range(100):
    if c[i] == 1:
        [x, y][j][i] += 1
        j = 1 - j
for i in range(100):
    if c[i] != 1:
        x[i] += c[i] // 2
        y[i] += c[i] // 2
        if c[i] % 2 == 1:
            [x, y][j][i] += 1
            j = 1 - j
xk = len(list([it for it in x if it]))
yk = len(list([it for it in y if it]))
print(xk * yk)
zs = [None] * (2*n)
for i in range(2*n):
    if x[a[i]] > 0:
        x[a[i]] -= 1
        zs[i] = 1
    else:
        assert y[a[i]] > 0
        y[a[i]] -= 1
        zs[i] = 2
print(*zs)


def s():
	input()
	l = [[]for _ in range(100)]
	a = list(map(int,input().split()))
	for i,v in enumerate(a):
		l[v].append(i)
	c = 0
	cc = 0
	fs = [0,0]
	for i in l:
		if len(i) == 0:
			continue
		if len(i) == 1:
			a[i[0]] = c+1
			fs[c]+=1
			c = 1 - c
			continue
		fs[c] += 1
		fs[c-1] += 1
		for e in i[:len(i)//2]:
			a[e] = 1 + cc
		for e in i[len(i)//2:]:
			a[e] = 2 - cc
		if len(i) % 2 == 1:
			cc = 1 - cc
	print(fs[0]*fs[1])
	print(*a)
s()

from collections import defaultdict as defdict

n = int(input())

d = defdict(int)
a = list(map(int, input().split()))

for i in a:
    d[i] += 1

b = set(i for i in a if d[i] > 1)
c = [i for i in a if d[i] == 1]

##print('b =', b)

mx = len(b) + (len(c) // 2)

d = defdict(int)
answ = [None] * (n * 2)

cnt_diff_1 = 0
cnt_diff_2 = 0

for i, x in enumerate(a):
    if cnt_diff_1 < mx:
        if x in b:
            if d[x] == 0:
                answ[i] = '1'
                d[x] += 1
                cnt_diff_1 += 1

for i, x in enumerate(a):
    if cnt_diff_1 < mx:
        if x not in b:
            answ[i] = '1'
            cnt_diff_1 += 1

##print(d)
cnt1 = cnt_diff_1
cnt2 = 0

##print(cnt_diff_1)
##print(answ)
##print(mx)

for i, x in enumerate(a):
    if answ[i] == '1': continue
    if x in b:
        if d[x] == 0:
            answ[i] = '2'
            d[x] = 2
            cnt_diff_2 += 1
            cnt2 += 1
        elif d[x] == 1:
            answ[i] = '2'
            d[x] += 1
            cnt_diff_2 += 1
            cnt2 += 1
        else:
            if cnt1 < n:
                answ[i] = '1'
                cnt1 += 1
            else:
                answ[i] = '2'
                cnt2 += 1
    else:
        if cnt2 < n:
            answ[i] = '2'
            cnt2 += 1
            cnt_diff_2 += 1
        else:
            answ[i] = '1'
            cnt1 += 1
##            print('cnt2 =', cnt2)
##            print(cnt_diff_2)
##            print('cnt1 =', cnt1)
            cnt_diff_1 += 1

##print(cnt_diff_1, cnt_diff_2)
##print()

##cnt1 = len(set(a[i] for i in range(2 * n) if answ[i] == '1'))
##cnt2 = len(set(a[i] for i in range(2 * n) if answ[i] == '2'))
##print(cnt1, cnt2)
print(cnt_diff_1 * cnt_diff_2)
print(' '.join(answ))


n = int(input())
a = list(map(int, input().split()))
R = range(100)
c = [[] for _ in [0]*100]
for i in range(n*2):
	c[a[i]].append(i)
d = [0]*200
heap = 1
z = [0, 0, 0]
for i in R:
	if len(c[i]) == 1:
		z[heap]+=1
		d[c[i][0]] = heap
		heap = 3 - heap;
for i in R:
	if len(c[i]) > 1:
		z[1]+=1
		z[2]+=1
		while len(c[i]):
			d[c[i].pop()] = heap
			heap = 3 - heap

print(z[1]*z[2])
print(' '.join(map(str, d[:n*2])))

n = int(input())
a = list(map(int, input().split()))
R = list(range(100))
c = [[] for _ in [0]*100]
for i in range(n*2):
	c[a[i]].append(i)
d = [0]*200
heap = 1
z = [0, 0, 0]
for i in R:
	if len(c[i]) == 1:
		z[heap]+=1
		d[c[i][0]] = heap
		heap = 3 - heap;
for i in R:
	if len(c[i]) > 1:
		z[1]+=1
		z[2]+=1
		while len(c[i]):
			d[c[i].pop()] = heap
			heap = 3 - heap

print(z[1]*z[2])
print(' '.join(map(str, d[:n*2])))



# Made By Mostafa_Khaled


n = int(input())
arr = list(map(int, input().split()))
adj = [[] for i in range(100)]
for i in range(2*n):
	adj[arr[i]].append(i)
res = [0] * (2 * n)
mul, curr = [], 1
x = [0, 0]
for i in range(10, 100):
	if len(adj[i]) == 1 :
		res[adj[i][0]] = curr
		x[curr-1] += 1
		curr = 3 - curr
	if len(adj[i]) > 1: 
		res[adj[i][0]] = 1
		res[adj[i][1]] = 2
		x[0] += 1
		x[1] += 1
		for j in range(2, len(adj[i])):
			mul.append(adj[i][j])
for i in range(len(mul)):
	res[mul[i]] = curr
	curr = 3 - curr
print(x[0] * x[1])
print(*res)


from collections import *
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
for i in range(2*n):
	a[i] = [a[i],i]
a.sort()
ans = [0 for i in range(2*n)]
da, db = {}, {}
f = 0
for i in range(2*n):
	if(c[a[i][0]] == 1): continue
	ans[a[i][1]] = f + 1
	if(f&1):
		da[a[i][0]] = 1
	else:
		db[a[i][0]] = 1
	f ^= 1
for i in range(2*n):
	if(ans[a[i][1]] != 0): continue
	ans[a[i][1]] = f+1
	if(f&1):
		da[a[i][0]] = 1
	else:
		db[a[i][0]] = 1
	f ^= 1
print(len(da)*len(db))
print(*ans)


n=int(input())
arr=list(map(int,input().split()))
g=[[] for i in range(100)]
for i in range(2*n):
    g[arr[i]].append(i)
x=0
y=0
curr=1
r=[]
for i in range(10,100):
    if len(g[i])==1:
        arr[g[i][0]]=curr
        if curr==1:
            x+=1
        else:
            y+=1
        curr=3-curr
    if len(g[i])>1:
        arr[g[i][0]]=1
        arr[g[i][1]]=2
        x+=1
        y+=1
        for j in range(2,len(g[i])):
            r.append(g[i][j])
for i in range(len(r)):
    arr[r[i]]=2-(i%2)
print(x*y)
print(*arr)

n=int(input())
arr=list(map(int,input().split()))
g=[[] for i in range(100)]
for i in range(2*n):
    g[arr[i]].append(i)
x=0
y=0
curr=1
flip=2
for i in range(10,100):
    if len(g[i])==1:
        arr[g[i][0]]=curr
        if curr==1:
            x+=1
        else:
            y+=1
        curr=3-curr
    if len(g[i])>1:
        arr[g[i][0]]=1
        arr[g[i][1]]=2
        x+=1
        y+=1
        for j in range(2,len(g[i])):
            arr[g[i][j]]=flip
            flip=3-flip
print(x*y)
print(*arr)


from sys import stdin

n = int(stdin.readline())
a = [int(x) for x in stdin.readline().split()]
a = sorted([(a[x], x) for x in range(n*2)])

group = {}

for x,ind in a:
    if x in group:
        group[x].append(ind)
    else:
        group[x] = [ind]

g2 = []

for x in group:
    g2.append([len(group[x]), group[x]])

g2.sort()

left = 0
right = 0

board = [0 for x in range(n*2)]

ind = 0
for x,l in g2:
    if x == 1:
        ind += 1
        if left <= right:
            left += 1
            board[l[0]] = '1'
        else:
            right += 1
            board[l[0]] = '2'
    else:
        break

if right > left:
    turn = True
else:
    turn = False

for x,l in g2[ind:]:
    left += 1
    right += 1

    if x%2 == 1:
        last = l.pop()
        if turn:
            board[last] = '1'
        else:
            board[last] = '2'
        turn = not turn
    for n in l[::2]:
        board[n] = '1'
    for n in l[1::2]:
        board[n] = '2'
print(left*right)
print(' '.join(board))