A team of students from the city S is sent to the All-Berland Olympiad in Informatics. Traditionally, they go on the train. All students have bought tickets in one carriage, consisting of n compartments (each compartment has exactly four people). We know that if one compartment contain one or two students, then they get bored, and if one compartment contain three or four students, then the compartment has fun throughout the entire trip.

The students want to swap with other people, so that no compartment with students had bored students. To swap places with another person, you need to convince him that it is really necessary. The students can not independently find the necessary arguments, so they asked a sympathetic conductor for help. The conductor can use her life experience to persuade any passenger to switch places with some student.

However, the conductor does not want to waste time persuading the wrong people, so she wants to know what is the minimum number of people necessary to persuade her to change places with the students. Your task is to find the number. 

After all the swaps each compartment should either have no student left, or have a company of three or four students. 


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^6) — the number of compartments in the carriage. The second line contains n integers a_1, a_2, ..., a_{n} showing how many students ride in each compartment (0 ≤ a_{i} ≤ 4). It is guaranteed that at least one student is riding in the train.


-----Output-----

If no sequence of swapping seats with other people leads to the desired result, print number "-1" (without the quotes). In another case, print the smallest number of people you need to persuade to swap places.


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

Output
2

Input
3
4 1 1

Output
2

Input
4
0 3 0 4

Output
0

Difficulty: HARD
Tags: Constructive algorithms

Combinatorics

Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
n = int(input())
counts = [0] * 5
s = 0
for x in [int(x) for x in input().split()]:
	counts[x] += 1
	s += x
if s > 2 and s != 5:
	ans = 0
	if counts[1] >= counts[2]:
		ans += counts[2]
		counts[3] += counts[2]
		counts[1] -= counts[2]
		ans += 2 * (counts[1] // 3)
		counts[3] += counts[1] // 3
		counts[1] %= 3
		if counts[3] > 0:
			ans += counts[1]
		elif counts[1] != 0:
			ans += 2
	else:
		ans += counts[1]
		counts[2] -= counts[1]
		ans += 2 * (counts[2] // 3)
		counts[2] %= 3
		if counts[4] > 0:
			ans += counts[2]
		elif counts[2] != 0:
			ans += 2
	print(ans)
else:
	print(-1)


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 math
from collections import Counter
import math
import bisect
n = int(input())
arr = list(map(int, input().split()))
f = 0
if sum(arr) < 3 or sum(arr) == 5:
	f = 1
a = arr.count(4)
b = arr.count(3)
c = arr.count(2)
d = arr.count(1)
var = min(c, d)
d -= var
c -= var
b += var
ans = var
if c:
	add = c // 3
	ans += 2 * add
	b += 2 * add
	c = c % 3
	ans += 1 if c == 1 and a >= 1 else 2 if c else 0
if d:
	add = d // 3
	ans += 2 * add
	b += add
	d = d % 3
	ans += 1 if b and d == 1 else 2 if d else 0
print(ans if f == 0 else -1)


n = int(input())
seq = list(map(int, input().split(' ')))
if sum(seq) < 3 or sum(seq) == 5:
	print(-1)
else:
	arr = [0, 0, 0, 0, 0]
	for s in seq:
		arr[s] += 1
	ans = 0
	if arr[2] >= arr[1]:
		ans += arr[1]
		arr[2] -= arr[1]
		arr[3] += arr[1]
		arr[1] = 0
	else:
		ans += arr[2]
		arr[1] -= arr[2]
		arr[3] += arr[2]
		arr[2] = 0
	ans += 2 * (arr[1] // 3)
	arr[3] += arr[1] // 3
	arr[1] %= 3
	if arr[3] >= arr[1]:
		ans += arr[1]
		arr[4] += arr[1]
		arr[3] -= arr[1]
		arr[1] = 0
	elif arr[1] < 2:
		ans += arr[3]
		arr[4] += arr[3]
		arr[1] -= arr[3]
		arr[3] = 0
	if arr[1] > 0:
		if arr[1] == 2:
			ans += arr[1]
			arr[4] -= 1
			arr[3] += 2
			arr[1] = 0
		else:
			ans += 2
			arr[4] -= 2
			arr[3] += 2
			arr[1] = 0
	ans += 2 * (arr[2] // 3)
	arr[3] += 2 * (arr[2] // 3)
	arr[2] %= 3
	if arr[2] > 0:
		if arr[4] >= arr[2]:
			ans += arr[2]
			arr[4] -= arr[2]
			arr[3] += 2 * arr[2]
			arr[2] = 0
			ans += 2 * arr[2]
			arr[4] += 2 * arr[2]
			arr[3] -= arr[2]
			arr[2] = 0
		elif arr[4] > 0:
			ans += arr[2]
			arr[4] -= arr[2]
			arr[3] += 2 * arr[2]
			arr[2] = 0
		elif arr[2] == 1:
			ans += 2 * arr[2]
			arr[3] += 2
			arr[2] = 0
		else:
			ans += arr[2]
			arr[4] += 1
			arr[2] = 0
	print(ans)


n = int(input())
A = [0, 0, 0, 0, 0]
B = list(map(int, input().split(' ')))
for i in B:
	A[i] += 1
res = min(A[1], A[2])
A[1] -= res
A[2] -= res
A[3] += res
res += 2 * (A[1] // 3)
A[3] += A[1] // 3
A[1] %= 3
res += 2 * (A[2] // 3)
A[3] += 2 * (A[2] // 3)
A[2] %= 3
assert A[1] == 0 or A[2] == 0
if A[1] == 1:
	if A[3] > 0:
		res += 1
	elif A[4] > 1:
		res += 2
	else:
		print(-1)
		return
elif A[1] == 2:
	if A[4] > 0:
		res += 2
	elif A[3] > 1:
		res += 2
	else:
		print(-1)
		return
if A[2] == 1:
	if A[4] > 0:
		res += 1
	elif A[3] > 1:
		res += 2
	else:
		print(-1)
		return
elif A[2] == 2:
	res += 2
print(res)


a = [0] * 5
(tot, ans) = (0, 0)
input()
for x in list(map(int, input().split())):
	a[x] += 1
	tot += x
if tot < 3 or tot == 5:
	exit(print(-1))
mn = min(a[1], a[2])
a[1] -= mn
a[2] -= mn
a[3] += mn
ans += mn
if a[1]:
	add = a[1] // 3
	a[1] %= 3
	a[3] += add
	ans += 2 * add
	ans += 1 if a[1] == 1 and a[3] else 2 if a[1] else 0
if a[2]:
	add = a[2] // 3
	a[2] %= 3
	a[3] += 2 * add
	ans += 2 * add
	ans += 1 if a[2] == 1 and a[4] else 2 if a[2] else 0
print(ans)