input = [80, 87, 10, 122, 57, 142, 134, 59, 113, 139, 101, 41, 138, 112, 46, 96, 43, 125, 36, 54, 133, 17, 42, 98, 7, 114, 78, 67, 77, 28, 149, 58, 20, 105, 31, 19, 18, 27, 40, 71, 117, 66, 21, 72, 146, 90, 97, 94, 123, 1, 119, 30, 84, 61, 91, 118, 2, 29, 104, 73, 13, 76, 24, 148, 68, 111, 131, 83, 49, 8, 132, 9, 64, 79, 124, 95, 88, 135, 3, 51, 39, 6, 60, 108, 14, 35, 147, 89, 34, 65, 50, 145, 128]
input.sort()
import math

def part1():
	diffs = [y - x for x, y in zip([0]+input,input+[input[-1]+3])]
	return diffs.count(1)*diffs.count(3)

def part2():
	current_one_group_size = 0
	current_two_group_size = 0
	total_permutations = 1
	permutations_cache = {}
	for x, y in zip([0]+input,input+[input[-1]+3]):
		diff = y - x
		if diff == 1:
			current_one_group_size +=1
		elif diff == 2:
			current_two_group_size +=1
		elif current_one_group_size + current_two_group_size > 0:
			if (current_one_group_size, current_two_group_size) in permutations_cache:
				current_loop_permutations = permutations_cache[(current_one_group_size, current_two_group_size)]
			else:
				total_group_size = current_one_group_size + 2 * current_two_group_size
				current_loop_permutations = 0
				for num_threes in range(int(total_group_size / 3) + 1):
					for num_twos in range(current_two_group_size, int((total_group_size - 3 * num_threes) / 2) + 1):
						num_ones = total_group_size - 3 * num_threes - 2 * num_twos
						current_loop_permutations += math.factorial(num_ones + num_twos + num_threes) / (math.factorial(num_ones) * math.factorial(num_twos) * math.factorial(num_threes))
				permutations_cache[(current_one_group_size,current_two_group_size)] = current_loop_permutations
			total_permutations *= current_loop_permutations
			current_one_group_size = 0
			current_two_group_size = 0
	return int(total_permutations)

print(part1())
print(part2())