As meticulous Gerald sets the table and caring Alexander sends the postcards, Sergey makes snowmen. Each showman should consist of three snowballs: a big one, a medium one and a small one. Sergey's twins help him: they've already made n snowballs with radii equal to r1, r2, ..., rn. To make a snowman, one needs any three snowballs whose radii are pairwise different. For example, the balls with radii 1, 2 and 3 can be used to make a snowman but 2, 2, 3 or 2, 2, 2 cannot. Help Sergey and his twins to determine what maximum number of snowmen they can make from those snowballs.

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of snowballs. The next line contains n integers — the balls' radii r1, r2, ..., rn (1 ≤ ri ≤ 109). The balls' radii can coincide.

Output

Print on the first line a single number k — the maximum number of the snowmen. Next k lines should contain the snowmen's descriptions. The description of each snowman should consist of three space-separated numbers — the big ball's radius, the medium ball's radius and the small ball's radius. It is allowed to print the snowmen in any order. If there are several solutions, print any of them.

Examples

Input

7
1 2 3 4 5 6 7


Output

2
3 2 1
6 5 4


Input

3
2 2 3


Output

0

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Greedy algorithms


Solutions:
from heapq import *
from collections import defaultdict
n = int(input())
r = map(int, input().split())
H = defaultdict(int)
for t in r:
	H[t] += 1
D = [(-1 * v, k) for (k, v) in H.items()]
heapify(D)
ret = []
while len(D) > 2:
	(a, b, c) = (heappop(D), heappop(D), heappop(D))
	ret.append(sorted([a[1], b[1], c[1]], reverse=True))
	for (x, xi) in ((i + 1, j) for (i, j) in (a, b, c)):
		if x:
			heappush(D, (x, xi))
print(len(ret))
for (a, b, c) in ret:
	print(a, b, c)


import heapq
n = int(input())
ara = list(map(int, input().split()))
mp = {}
ans = []
pq = []
for val in ara:
	mp.setdefault(val, 0)
	mp[val] += 1
for k in mp:
	heapq.heappush(pq, [-mp[k], k])
while len(pq) >= 3:
	val = [None] * 3
	val[0] = heapq.heappop(pq)
	val[1] = heapq.heappop(pq)
	val[2] = heapq.heappop(pq)
	ans.append([val[0][1], val[1][1], val[2][1]])
	for i in range(3):
		if val[i][0] != -1:
			val[i][0] += 1
			heapq.heappush(pq, val[i])
print(len(ans))
for ro in ans:
	ro.sort(reverse=True)
	for val in ro:
		print(val, end=' ')
	print()


from sys import stdin
import heapq
n = int(stdin.readline())
balls = [int(x) for x in stdin.readline().split()]
balls.sort()
counts = {}
for x in balls:
	if x in counts:
		counts[x] += 1
	else:
		counts[x] = 1
q = []
for x in counts:
	heapq.heappush(q, [-counts[x], x])
snowmen = []
while len(q) >= 3:
	a = heapq.heappop(q)
	b = heapq.heappop(q)
	c = heapq.heappop(q)
	a[0] += 1
	b[0] += 1
	c[0] += 1
	s = [str(x) for x in sorted([a[1], b[1], c[1]], reverse=True)]
	snowmen.append(s)
	if a[0] < 0:
		heapq.heappush(q, a)
	if b[0] < 0:
		heapq.heappush(q, b)
	if c[0] < 0:
		heapq.heappush(q, c)
print(len(snowmen))
for x in snowmen:
	print(' '.join(x))


import os
import sys
from io import BytesIO, IOBase
import math
import itertools
import bisect
import heapq

def main():
	pass
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')

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countcon(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def lis(arr):
	n = len(arr)
	lis = [1] * n
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
	maximum = 0
	for i in range(n):
		maximum = max(maximum, lis[i])
	return maximum

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def maxfac(n):
	root = int(n ** 0.5)
	for i in range(2, root + 1):
		if n % i == 0:
			return n // i
	return n

def p2(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def seive(n):
	primes = [True] * (n + 1)
	primes[1] = primes[0] = False
	for i in range(2, n + 1):
		if primes[i]:
			for j in range(i + i, n + 1, i):
				primes[j] = False
	p = []
	for i in range(0, n + 1):
		if primes[i]:
			p.append(i)
	return p

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def denofactinverse(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return pow(fac, m - 2, m)

def numofact(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return fac

def sumnum(n):
	s = 0
	for i in str(n):
		s += int(i)
	return s
n = int(input())
l = list(map(int, input().split()))
d = {}
for i in l:
	if i not in d:
		d.update({i: 1})
	else:
		d[i] += 1
l = []
for i in d:
	l.append([-d[i], i])
l.sort()
ans = []
while len(l) > 2:
	(t1, t2, t3) = (heapq.heappop(l), heapq.heappop(l), heapq.heappop(l))
	ans.append([t1[1], t2[1], t3[1]])
	if t1[0] < -1:
		t1[0] += 1
		heapq.heappush(l, t1)
	if t2[0] < -1:
		t2[0] += 1
		heapq.heappush(l, t2)
	if t3[0] < -1:
		t3[0] += 1
		heapq.heappush(l, t3)
print(len(ans))
for i in ans:
	i.sort(reverse=True)
	print(*i)


from heapq import *
from collections import defaultdict
n = int(input())
r = map(int, input().split())
assoc = defaultdict(int)
for ballsize in r:
	assoc[ballsize] += 1
available = [(-1 * val, key) for (key, val) in assoc.items()]
heapify(available)
ret = []
while len(available) > 2:
	(a, b, c) = (heappop(available), heappop(available), heappop(available))
	ret.append(sorted([a[1], b[1], c[1]], reverse=True))
	for (i, j) in (a, b, c):
		(x, xi) = (i + 1, j)
		if x:
			heappush(available, (x, xi))
print(len(ret))
for (a, b, c) in ret:
	print(a, b, c)


from collections import Counter
from heapq import heappop, heappush, heapify
n = int(input())
A = list(map(int, input().split()))
z = Counter(A)
A = list(set(A))
A.sort(reverse=True)
t = 0
p = len(A)
if p < 3:
	print(0)
else:
	Heap = []
	Ans = []
	for i in A:
		Heap.append((-z[i], i))
	heapify(Heap)
	while len(Heap) > 2:
		a = heappop(Heap)
		b = heappop(Heap)
		c = heappop(Heap)
		Ans.append(sorted([a[1], b[1], c[1]])[::-1])
		if a[0] + 1 != 0:
			heappush(Heap, (a[0] + 1, a[1]))
		if b[0] + 1 != 0:
			heappush(Heap, (b[0] + 1, b[1]))
		if c[0] + 1 != 0:
			heappush(Heap, (c[0] + 1, c[1]))
	print(len(Ans))
	for i in Ans:
		print(*i)


from collections import defaultdict
(n, t) = (int(input()), input().split())
p = defaultdict(int)
for i in t:
	p[i] += 1
if len(p) < 3:
	print(0)
else:
	q = list(p.items())
	(a, b) = (q[0][1], q[1][1])
	(x, y) = (0, 1)
	if a < b:
		(x, y, a, b) = (y, x, b, a)
	for i in range(2, len(q)):
		if q[i][1] > b:
			if q[i][1] > a:
				(x, y, a, b) = (i, x, q[i][1], a)
			else:
				(y, b) = (i, q[i][1])
	k = n // 3
	if a > k:
		(c, s) = (n - a - b, n - a)
		if c > b:
			(q[x], q[y], k) = ((q[x][0], s >> 1), (q[y][0], b - (s & 1)), s >> 1)
		else:
			(q[x], q[y], k) = ((q[x][0], c), (q[y][0], c), c)
	q = [(int(x), y) for (x, y) in q]
	q.sort(reverse=True)
	(p, n) = ([], 2 * k)
	for i in q:
		p += [str(i[0]) + ' '] * i[1]
	print(k)
	print('\n'.join((p[i] + p[k + i] + p[n + i] for i in range(k))))


import heapq
from collections import defaultdict
n = int(input())
b = list(map(int, input().split()))
cnt = defaultdict(lambda : 0)
for j in b:
	cnt[j] += 1
li = []
for j in list(set(b)):
	li.append([-cnt[j], j])
heapq.heapify(li)
l = len(li)
ans = []
while l >= 3:
	ball1 = heapq.heappop(li)
	ball2 = heapq.heappop(li)
	ball3 = heapq.heappop(li)
	ans.append([ball1[1], ball2[1], ball3[1]])
	cnt1 = ball1[0] + 1
	if cnt1 != 0:
		heapq.heappush(li, [cnt1, ball1[1]])
	else:
		l += -1
	cnt2 = ball2[0] + 1
	if cnt2 != 0:
		heapq.heappush(li, [cnt2, ball2[1]])
	else:
		l += -1
	cnt3 = ball3[0] + 1
	if cnt3 != 0:
		heapq.heappush(li, [cnt3, ball3[1]])
	else:
		l += -1
print(len(ans))
for j in ans:
	j.sort()
	print(*j[::-1])


import sys
import math
n = int(sys.stdin.readline())
r = [int(x) for x in sys.stdin.readline().strip().split()]
r = sorted(r)
a = 0
b = n // 3
d = {key: 0 for key in r}
for i in range(n):
	d[r[i]] += 1
while a != b:
	k = math.ceil((a + b) / 2)
	rp = 0
	for i in d:
		rp += min(k, d[i])
	if rp < 3 * k:
		b = k - 1
	else:
		a = k
k = a
sys.stdout.write(str(k) + '\n')
rp = []
for i in d:
	rp += [i] * min(k, d[i])
rp = sorted(rp)
i = 0
for p in range(k):
	sys.stdout.write('{} {} {}\n'.format(rp[i + 2 * k], rp[i + k], rp[i]))
	i += 1


import heapq
n = int(input())
arr = list(map(int, input().split()))
(mp, res, pq) = ({}, [], [])
for val in arr:
	mp.setdefault(val, 0)
	mp[val] += 1
for k in mp:
	heapq.heappush(pq, [-mp[k], k])
while len(pq) >= 3:
	val = [0] * 3
	val[0] = heapq.heappop(pq)
	val[1] = heapq.heappop(pq)
	val[2] = heapq.heappop(pq)
	res.append([val[0][1], val[1][1], val[2][1]])
	for i in range(3):
		if val[i][0] != -1:
			val[i][0] += 1
			heapq.heappush(pq, val[i])
print(len(res))
for i in res:
	print(*sorted(i, reverse=True))


from collections import Counter as c
from heapq import *
input()
a = dict(c([int(x) for x in input().split()]))
d = [(-1 * v, k) for (k, v) in a.items()]
heapify(d)
ans = []
while len(d) > 2:
	(a, b, c) = (heappop(d), heappop(d), heappop(d))
	ans.append(sorted([a[1], b[1], c[1]], reverse=True))
	for (x, y) in (a, b, c):
		if x + 1:
			heappush(d, (x + 1, y))
print(len(ans))
for x in ans:
	print(*x)


import heapq
n = int(input())
a = {}
for r in map(int, input().split()):
	a[r] = a.get(r, 0) - 1
b = []
for r in a:
	b.append((a[r], r))
heapq.heapify(b)
(ans, k) = ([], 0)
while len(b) > 2:
	k += 1
	c = [heapq.heappop(b), heapq.heappop(b), heapq.heappop(b)]
	ans.append([c[0][1], c[1][1], c[2][1]])
	for z in c:
		if z[0] < -1:
			heapq.heappush(b, (z[0] + 1, z[1]))
print(k)
for z in ans:
	z.sort(reverse=True)
	print(*z)


from io import BytesIO
import os
from collections import Counter
import heapq
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
	count = int(input())
	balls = list(map(int, input().split()))
	counter = Counter(balls)
	pq = []
	for (value, count) in counter.items():
		heapq.heappush(pq, (-count, value))
	ans = []
	while len(pq) > 2:
		first = heapq.heappop(pq)
		second = heapq.heappop(pq)
		third = heapq.heappop(pq)
		ans.append(sorted([first[1], second[1], third[1]], reverse=True))
		if first[0] < -1:
			heapq.heappush(pq, (first[0] + 1, first[1]))
		if second[0] < -1:
			heapq.heappush(pq, (second[0] + 1, second[1]))
		if third[0] < -1:
			heapq.heappush(pq, (third[0] + 1, third[1]))
	print(len(ans))
	for snowman in ans:
		print(*snowman)
main()


from collections import defaultdict
from heapq import *
n = int(input())
bumbas = list(map(int, input().split()))
bumbu_skaits = defaultdict(int)
for b in bumbas:
	bumbu_skaits[b] += 1
pieejamaas = []
sniegaviri = []
for (a, v) in bumbu_skaits.items():
	pieejamaas.append((v * -1, a))
heapify(pieejamaas)
while len(pieejamaas) > 2:
	(a, b, c) = (heappop(pieejamaas), heappop(pieejamaas), heappop(pieejamaas))
	sniegaviri.append(sorted([a[1], b[1], c[1]], reverse=True))
	for (i, j) in (a, b, c):
		jaunaissk = i + 1
		if jaunaissk != 0:
			heappush(pieejamaas, (jaunaissk, j))
print(len(sniegaviri))
for (a, b, c) in sniegaviri:
	print(a, b, c)