The Tower of Hanoi is a famous game consisting of $3$ rods and a number of discs of incrementally different diameters. The puzzle starts with the discs neatly stacked on one rod, ordered by ascending size with the smallest disc at the top. The game's objective is to move the entire stack to another rod, obeying the following rules:

Only one disk can be moved at a time.
In one move, remove the topmost disk from one rod and move it to another rod.  
No disk may be placed on top of a smaller disk.

Gena has a modified version of the Tower of Hanoi. This game of Hanoi has $4$ rods and $n$ disks ordered by ascending size. Gena has already made a few moves following the rules above. Given the state of Gena's Hanoi, determine the minimum number of moves needed to restore the tower to its original state with all disks on rod $1$.  

Note: Gena's rods are numbered from $1$ to $4$. The radius of a disk is its index in the input array, so disk $1$ is the smallest disk with a radius of $1$, and disk $n$ is the largest with a radius of $n$.  

Example 

$posts=[4,3,2,1]$  

In this case, the disks are arranged from large to small across the four rods.  The largest disk, disk $4$, is already on rod $1$, so move disks $3,2$ and $1$ to rod $1$, in that order.  It takes $3$ moves to reset the game.  

$posts=[4,2,2,1]$  

The largest disk, disk $4$ with radius $4$, is already on rod $1$.  Disk $3$ is on rod $2$ and must be below disk $2$.  Move disk $2$ to rod $3$, disk $3$ to rod $1$ and disk $2$ to rod $1$.  Now move disk $1$ to rod $1$.  It takes $3$ moves to reset the game.  

Function Description   

Complete the hanoi function below.  

hanoi has the following parameters:  

int posts[n]: $posts[i]$ is the location of the disk with radius $\boldsymbol{i}$  

Returns  

int:  the minimum moves to reset the game to its initial state  

Input Format

The first line contains a single integer, $n$, the number of disks. 

The second line contains $n$ space-separated integers, where the $i^{\mbox{th}}$ integer is the index of the rod where the disk with diameter $\boldsymbol{i}$ is located.

Constraints

$1\leq n\leq10$

Sample Input
STDIN   Function
-----   --------
3       size of posts[] n = 3
1 4 1   posts = [1, 4, 1]

Sample Output
3

Explanation

$3$ moves are enough to build the tower. Here is one possible solution:

Source: hackerrank | Difficulty: MEDIUM
Tags: Complete search


Solutions:
import sys

def getRod(position, disc):
	return position >> disc * 2 & 3

def setRod(position, disc, rod):
	position = position & ~(3 << disc * 2) | rod << disc * 2
	return position

def getPosition(rods):
	position = 0
	for i in range(len(rods)):
		position = setRod(position, i, rods[i])
	return position

def getRods(position):
	return [getRod(position, disc) for disc in range(N)]
N = int(input().strip())
a = [int(a_temp) - 1 for a_temp in input().strip().split(' ')]
searchQueue = [getPosition(a)]
distances = {getPosition(a)}
currentDistance = 0
targetPosition = 0
while targetPosition not in distances and len(searchQueue):
	oldSearchQueue = searchQueue
	searchQueue = []
	currentDistance += 1
	for position in oldSearchQueue:
		topDisc = [100, 100, 100, 100]
		for i in range(N - 1, -1, -1):
			rod = position >> i * 2 & 3
			topDisc[rod] = i
		for rod1 in range(4):
			for rod2 in range(4):
				if rod1 != rod2 and topDisc[rod1] < topDisc[rod2]:
					disc = topDisc[rod1]
					newPosition = position & ~(3 << disc * 2) | rod2 << disc * 2
					if newPosition not in distances:
						searchQueue.append(newPosition)
						distances.add(newPosition)
print(currentDistance)


import sys

def generate(move, N):
	next = []
	i = 0
	available = [1, 2, 3, 4]
	while i < N:
		if len(available) == 0:
			break
		elif move[i] in available:
			available.remove(move[i])
		else:
			i = i + 1
			continue
		for m in available:
			amove = list(move)
			amove[i] = m
			next.append(tuple(amove))
		i = i + 1
	return set(next)
N = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]
initial = []
i = 0
while i < N:
	initial.append(1)
	i = i + 1
moves = set()
moves.add(tuple(initial))
current = set(moves)
gen = 0
while True:
	next = set()
	for move in current:
		next.update(generate(move, N))
	gen = gen + 1
	next.difference_update(moves)
	moves.update(next)
	if tuple(a) in next:
		print(gen)
		break
	current = set(next)


import sys
MAX_MOVES = 100

def valid_moves(state, K):
	(pegs, tops) = ([-1] * K, [])
	for (r, peg) in enumerate(state):
		if pegs[peg] < 0:
			pegs[peg] = r
			for (top_r, top_peg) in tops:
				yield (top_r, top_peg, peg)
			tops.append((r, peg))
	for (dst_peg, peg_r) in enumerate(pegs):
		if peg_r < 0:
			for (top_r, top_peg) in tops:
				yield (top_r, top_peg, dst_peg)

def move_apply(state, move):
	(r, src, dst) = move
	return state[:r] + (dst,) + state[r + 1:]

def solve_bfs(initial_state, final_state, K):
	known_states = set()
	next_states = [(initial_state, [])]
	depth = 0
	while next_states and depth < MAX_MOVES:
		(states, next_states) = (next_states, [])
		for (state, moves) in states:
			for move in valid_moves(state, K):
				new_state = move_apply(state, move)
				if new_state in known_states:
					continue
				new_moves = moves + [move]
				if new_state == final_state:
					return new_moves
				next_states.append((new_state, new_moves))
				known_states.add(new_state)
		depth += 1
N = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split()]
initial_state = tuple((int(i) - 1 for i in a))
final_state = tuple((0 for _ in range(N)))
solution = solve_bfs(initial_state, final_state, 4)
if solution:
	print(len(solution))


from collections import deque

def sortPartial(state):
	(a, b, c) = sorted(state[1:])
	return (state[0], a, b, c)
N = int(input().strip())
target = [int(x) for x in input().split()]
target = sortPartial(tuple([tuple(sorted((i for (i, e) in enumerate(target) if e - 1 == k))) for k in range(4)]))

def move(state, i, j):
	res = []
	for (k, new) in enumerate(state):
		if k == i:
			new = new[1:]
		elif k == j:
			new = tuple([state[i][0]]) + new
		res.append(new)
	return sortPartial(tuple(res))

def performStep(state):
	for i in range(4):
		for j in range(4):
			if state[i] and (not state[j] or state[i][0] < state[j][0]):
				yield move(state, i, j)
initial = (tuple((i for i in range(N))), (), (), ())
done = set()
waitlist = deque()
waitlist.append((0, initial))
while waitlist:
	(step, next) = waitlist.popleft()
	if next in done:
		continue
	done.add(next)
	for p in performStep(next):
		if p == target:
			print(step + 1)
			exit()
		waitlist.append((step + 1, p))


import sys
n = int(input().strip())
A = [int(a_temp) for a_temp in input().strip().split(' ')]

def fewestmovesHanoi(n, A):
	if A == [1] * n:
		return 0
	forward = set(['1' * n])
	countf = 0
	reverse = set([''.join((str(a) for a in A))])
	countr = 0
	while True:
		if countf == countr:
			countf += 1
			newforward = set()
			for f in forward:
				ind = list()
				for rod in '1234':
					if rod in f:
						ind.append((f.index(rod), rod))
					else:
						ind.append((n, rod))
				ind = sorted(ind)
				while len(ind) > 1:
					(i, rod) = ind[0]
					if i != n:
						for j in range(1, len(ind)):
							newf = f[:i] + ind[j][1] + f[i + 1:]
							if newf in reverse:
								return countf + countr
							else:
								newforward.add(newf)
					ind.remove((i, rod))
			forward = newforward
		else:
			countr += 1
			newreverse = set()
			for r in reverse:
				ind = list()
				for rod in '1234':
					if rod in r:
						ind.append((r.index(rod), rod))
					else:
						ind.append((n, rod))
				ind = sorted(ind)
				while len(ind) > 1:
					(i, rod) = ind[0]
					if i != n:
						for j in range(1, len(ind)):
							newr = r[:i] + ind[j][1] + r[i + 1:]
							if newr in forward:
								return countf + countr
							else:
								newreverse.add(newr)
					ind.remove((i, rod))
			reverse = newreverse
print(fewestmovesHanoi(n, A))


N = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]
goal_state = (tuple(reversed(range(N))), tuple(), tuple(), tuple())
initial_state = [[], [], [], []]
for (i, rod) in enumerate(a):
	initial_state[rod - 1].insert(0, i)
initial_state = tuple((tuple(rod) for rod in initial_state))
initial_state = initial_state[:1] + tuple(sorted(initial_state[1:]))

def try_brute_force():
	moves = {}
	moves[initial_state] = 0
	state_queue = [initial_state]
	while len(state_queue) > 0:
		state = state_queue.pop(0)
		for src in range(4):
			if len(state[src]) > 0:
				src_size = state[src][-1]
				for dst in range(4):
					if src != dst and (len(state[dst]) == 0 or state[dst][-1] > src_size):
						new_state = list(state)
						new_state[src] = state[src][:-1]
						new_state[dst] = state[dst] + (src_size,)
						new_state = tuple(new_state[:1]) + tuple(sorted(new_state[1:]))
						if new_state not in moves:
							moves[new_state] = moves[state] + 1
							state_queue.append(new_state)
							if new_state == goal_state:
								return moves[new_state]
print(try_brute_force())


N = 10
a = [0] * (2 << 2 * N + 1)
b = [0] * 4
n = int(input())
K = 0
t = 0
for x in map(int, input().split()):
	K |= x - 1 << t * 2
	t += 1
a[0] = 1
Q = []
Q.append(0)
ind = 0
while True:
	x = Q[ind]
	ind += 1
	if x == K:
		print(a[x] - 1)
		exit(0)
	for i in range(4):
		b[i] = 1000
	for i in range(n - 1, -1, -1):
		b[3 & x >> i * 2] = i
	for i in range(4):
		for j in range(4):
			if b[i] < b[j]:
				y = x + (j - i << b[i] * 2)
				if a[y] == 0:
					a[y] = a[x] + 1
					Q.append(y)


from collections import deque
from functools import reduce
RODS_CNT = 4
DISK_CNT = None

def successors(s):
	rods = [-1] * RODS_CNT
	suc = []
	for i in range(DISK_CNT):
		v = s >> 2 * i & 3
		if rods[v] == -1 or rods[v] > i:
			rods[v] = i
	for i in [k for k in rods if k > -1]:
		for j in range(RODS_CNT):
			if rods[j] == -1 or rods[j] > i:
				ss = s & ~(3 << i * 2) | j << i * 2
				suc.append(ss)
	return suc

def search(start_state):
	q = deque([])
	q.append((start_state, 0))
	marked = [False] * 4 ** 10
	while True:
		(s, l) = q.popleft()
		if not marked[s]:
			if s == 0:
				return l
			else:
				marked[s] = True
				for i in successors(s):
					q.append((i, l + 1))
DISK_CNT = int(input())
start_state = reduce(lambda res, x: res << 2 | x, reversed([int(i) - 1 for i in input().split()]))
print(search(start_state))


import sys
from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


from collections import deque

def is_final(state):
	return all((len(x) == 0 for x in state[1:]))

def to_tuple(state):
	return tuple((tuple(x) for x in state))

def possible_moves(state):
	for i in range(len(state)):
		if state[i]:
			for j in range(len(state)):
				if not state[j] or state[i][-1] < state[j][-1]:
					yield (i, j)

def make_move(state, move):
	(m1, m2) = move
	new_state = [list(x) for x in state]
	new_state[m2].append(new_state[m1].pop())
	new_state[1:4] = sorted(new_state[1:4], key=lambda x: x[-1] if x else 0)
	return to_tuple(new_state)

def bfs(initial_state):
	moves = 0
	initial_state = to_tuple(initial_state)
	start = (initial_state, moves)
	queue = deque([start])
	visited = set(initial_state)
	while queue:
		(c_state, depth) = queue.popleft()
		if is_final(c_state):
			return depth
		for move in possible_moves(c_state):
			new_state = make_move(c_state, move)
			if new_state not in visited:
				visited.add(new_state)
				queue.append((new_state, depth + 1))
n = int(input())
rods = [[] for _ in range(4)]
pos = [int(x) for x in input().split()]
for (i, x) in enumerate(pos, 1):
	rods[x - 1] = [i] + rods[x - 1]
print(bfs(rods))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


def allowed_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def reached_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def tupler(z):
	z[1:4] = sorted(z[1:4], key=lambda t: t[-1] if t else 0)
	return tuple((tuple(t) for t in z))

def mover(g, m):
	y = [list(t) for t in g]
	y[m[1]].append(y[m[0]].pop())
	return tupler(y)

def bfs(x):
	visited = set()
	start = [tupler(x), 0]
	q = list([start])
	visited.add(start[0])
	while q:
		(node, depth) = q.pop(0)
		if reached_goal(node):
			return depth
		for move in allowed_moves(node):
			child = mover(node, move)
			if child not in visited:
				visited.add(child)
				q.extend([[child, depth + 1]])
N = int(input())
R = [int(t) for t in input().split()]
A = [[] for i in range(4)]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


__author__ = 'chrisgreening'
import sys
import heapq
N = int(input().strip())
indexes = [int(a_temp) for a_temp in input().strip().split(' ')]
rods = [[] for _ in range(4)]
for i in range(N):
	rods[indexes[i] - 1].append(i + 1)
for rod in rods:
	rod.sort(reverse=True)
explored_set = {}

def goal(rods):
	return len(rods[0]) == N

def doMove(rods, i, j):
	disk = rods[i].pop()
	rods[j].append(disk)
min_moves = 10000000
moves = 0

def explored():
	hash = []
	for r in rods:
		rod_hash = 0
		multipler = 1
		for rr in r:
			rod_hash = rod_hash + multipler * rr
			multipler *= 10
		hash.append(rod_hash)
	hash[1:4] = sorted(hash[1:4])
	hash_tuple = tuple(hash)
	if not hash_tuple in explored_set:
		explored_set[hash_tuple] = moves
		return False
	if moves < explored_set[hash_tuple]:
		explored_set[hash_tuple] = moves
		return False
	return True

def search():
	global moves
	global min_moves
	for i in range(4):
		if len(rods[i]) > 0:
			disk = rods[i][-1]
			for j in range(4):
				if i != j and (len(rods[j]) == 0 or rods[j][-1] > disk):
					doMove(i, j)
					moves += 1
					if goal(rods):
						min_moves = min(min_moves, moves)
					elif not explored():
						search()
					doMove(j, i)
					moves -= 1
	return False

def to_representation(rods):
	hash = []
	for r in rods:
		rod_hash = 0
		multipler = 1
		for rr in r:
			rod_hash = rod_hash + multipler * rr
			multipler *= 11
		hash.append(rod_hash)
	hash[1:4] = sorted(hash[1:4])
	return tuple(hash)

def from_representation(rep):
	rep2 = list(rep)
	rods = [[] for _ in range(4)]
	for i in range(4):
		while rep2[i] != 0:
			rods[i].append(rep2[i] % 11)
			rep2[i] //= 11
	return rods

def search2(rods):
	frontier = [(0, to_representation(rods))]
	heapq.heapify(frontier)
	explored = set()
	while len(frontier) > 0:
		front = heapq.heappop(frontier)
		if not front[1] in explored:
			explored.add(front[1])
			rods = from_representation(front[1])
			if goal(rods):
				return front[0]
			for i in range(4):
				if len(rods[i]) > 0:
					disk = rods[i][-1]
					for j in range(4):
						if i != j and (len(rods[j]) == 0 or rods[j][-1] > disk):
							doMove(rods, i, j)
							rep = to_representation(rods)
							if not rep in explored:
								heapq.heappush(frontier, (front[0] + 1, rep))
							doMove(rods, j, i)
print(search2(rods))


import sys
N = int(input().strip())
InitialLoc = [int(a_temp) for a_temp in input().strip().split(' ')]
import itertools as it
Transformations = list(it.permutations(range(4), 2))
nBlock = len(InitialLoc)
StateSize = 2 * nBlock
powersOf2 = [2 ** m for m in range(StateSize - 1, -1, -1)]
InitialLoc = [m - 1 for m in InitialLoc]
InitialState = ''.join(['0' + format(m, 'b') if m < 2 else format(m, 'b') for m in InitialLoc])
InitialState = int(InitialState, 2)
AlreadyVisited = [False for m in range(2 ** StateSize)]
AlreadyVisited[InitialState] = True

def GetBin(nIn):
	Output = []
	for i in powersOf2:
		if nIn >= i:
			nIn -= i
			Output.append(1)
		else:
			Output.append(0)
	return Output

def GetLegalResults(nIn):
	BinList = GetBin(nIn)
	Stacks = [[] for m in range(4)]
	for i in range(nBlock - 1, -1, -1):
		Stacks[BinList[i * 2] * 2 + BinList[i * 2 + 1]].append(i)
	LegalTransform = []
	for i in Transformations:
		if len(Stacks[i[0]]) > 0:
			if len(Stacks[i[1]]) == 0 and len(Stacks[i[0]]) > 1:
				LegalTransform.append(i)
			elif len(Stacks[i[1]]) > 0 and Stacks[i[0]][-1] < Stacks[i[1]][-1]:
				LegalTransform.append(i)
			elif min(i) == 0 and len(Stacks[i[1]]) == 0:
				LegalTransform.append(i)
	OutputStates = []
	for i in LegalTransform:
		BlockMoved = Stacks[i[0]][-1]
		StateDelta = 2 ** (2 * (nBlock - 1 - BlockMoved)) * (i[1] - i[0])
		OutputStates.append(nIn + StateDelta)
	return OutputStates
CurrentStates = [InitialState]
FoundSoln = False
Count = 0
while True:
	Count += 1
	NewStates = []
	for j in CurrentStates:
		for i in GetLegalResults(j):
			if i == 0:
				FoundSoln = True
				break
			if not AlreadyVisited[i]:
				AlreadyVisited[i] = True
				NewStates.append(i)
	if FoundSoln:
		break
	CurrentStates = NewStates
print(Count)


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


from collections import deque
from copy import deepcopy

def tuplify(L):
	return tuple((tuple(k) for k in L))

def listify(T):
	return list((list(k) for k in T))

def normalize(L):
	return L[:2] + sorted(L[2:])

def min_moves(N, start):
	q = deque()
	start = normalize(start)
	q.append((tuplify(start), 0))
	visited = set()
	end = [list() for i in range(5)]
	end[1] = list(range(1, N + 1))[::-1]
	end = tuplify(end)
	while q:
		(stacks, moves) = q.popleft()
		if stacks == end:
			return moves
		if stacks not in visited:
			visited.add(stacks)
			for from_idx in range(1, 4 + 1):
				for to_idx in range(1, 4 + 1):
					if len(stacks[from_idx]) == 0 or from_idx == to_idx:
						continue
					if len(stacks[to_idx]) == 0 or stacks[from_idx][-1] < stacks[to_idx][-1]:
						new_stacks = listify(stacks)
						disc = new_stacks[from_idx].pop()
						new_stacks[to_idx].append(disc)
						new_stacks = tuplify(normalize(new_stacks))
						if new_stacks not in visited:
							q.append((new_stacks, moves + 1))
N = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]
stacks = [list() for i in range(5)]
for i in range(len(a) - 1, -1, -1):
	stacks[a[i]].append(i + 1)
print(min_moves(N, stacks))


import sys
from collections import deque

def solve():
	N = int(input().strip())
	goal = tuple([0 for x in range(N)])
	a = tuple([int(a_temp) - 1 for a_temp in input().strip().split(' ')])
	if a == goal:
		print(0)
	else:
		(q, mark) = (deque(), set())
		mark.add(a)
		q.append((a, 0))
		while len(q):
			(l, d) = q.popleft()
			top = [100, 100, 100, 100]
			for idx in range(N):
				top[l[idx]] = min(top[l[idx]], idx)
			for x in range(4):
				for y in range(4):
					if x != y and top[x] < top[y]:
						t = list(l)
						t[top[x]] = y
						t = tuple(t)
						if t == goal:
							print(d + 1)
							return
						if t not in mark:
							mark.add(t)
							q.append((t, d + 1))
solve()


import sys
from collections import *
import itertools
possible_moves = [(0, 1), (0, 2), (0, 3), (1, 0), (1, 2), (1, 3), (2, 0), (2, 1), (2, 3), (3, 0), (3, 1), (3, 2)]
N = int(sys.stdin.readline().strip())
a = [int(a_temp) for a_temp in sys.stdin.readline().strip().split(' ')]
first_state = [[] for i in range(4)]
for i in range(N):
	first_state[a[i] - 1].append(i)
first_state.append([float('inf'), 0])
first_state = tuple((tuple(sorted(i, reverse=True)) for i in first_state))
visited = set(tuple([first_state[0]] + sorted(first_state[1:-1])))
pq = deque()
pq.appendleft(first_state)
while pq:
	curr_state = pq.pop()
	if curr_state[0] == tuple(range(N - 1, -1, -1)):
		print(curr_state[4][1])
		break
	for move in possible_moves:
		start = move[0]
		end = move[1]
		if curr_state[start] and (not curr_state[end] or curr_state[end][-1] > curr_state[start][-1]):
			new_state = []
			for (i, rod) in enumerate(curr_state):
				if i == start:
					new_state.append(rod[:-1])
				elif i == end:
					new_state.append(tuple(list(rod) + [curr_state[start][-1]]))
				elif i != 4:
					new_state.append(rod)
				else:
					new_state.append(tuple([float('inf'), rod[1] + 1]))
			new_state = tuple([new_state[0]] + sorted(new_state[1:]))
			if new_state[:-1] not in visited:
				pq.appendleft(new_state)
				visited.add(new_state[:-1])


N = int(input().strip())
a = [int(_) - 1 for _ in input().split(' ')]
rep = [''] * 4
for ii in range(N):
	rep[a[ii]] += str(ii)
rep[0] += ';'
for ii in range(1, 4):
	rep[ii] += ':'
rep.sort()
key = ''.join(rep)
used = set([key])
moves = [[][:]] * 6
(bfs, substr, count) = ([rep], str(N - 1) + ';', 0)
while substr[0] > '0':
	substr = chr(ord(substr[0]) - 1) + substr
substr += ':::'
finished = False
while not finished:
	count += 1
	new_bfs = list()
	while bfs:
		entry = bfs.pop()
		moves[0] = ['0' + entry[1], entry[0][1:], entry[2], entry[3]]
		moves[1] = ['0' + entry[2], entry[0][1:], entry[1], entry[3]]
		moves[2] = ['0' + entry[3], entry[0][1:], entry[1], entry[2]]
		moves[3] = [entry[0], entry[1][1:], entry[1][0] + entry[2], entry[3]]
		moves[4] = [entry[0], entry[1][1:], entry[2], entry[1][0] + entry[3]]
		moves[5] = [entry[0], entry[1], entry[2][1:], entry[2][0] + entry[3]] if len(entry[2]) > 1 else []
		for mv in moves:
			if mv:
				mv.sort()
				key = ''.join(mv)
				if key not in used:
					if key == substr:
						finished = True
					else:
						used.add(key)
						new_bfs.append(mv)
	bfs = new_bfs
print(count)


N = int(input().strip())
bitfull = 4 ** N - 1

def move(state, size, rto):
	shift = (size - 1) * 2
	mask = 3 << shift
	invmask = bitfull ^ mask
	rbit = rto << shift
	return state & invmask | rbit

def getmins(state):
	mins = [N + 1] * 4
	size = 1
	mask = 3
	found = 0
	while found < 4 and size <= N:
		rod = state & mask
		if mins[rod] > N:
			found += 1
			mins[rod] = size
		state >>= 2
		size += 1
	return mins

def BFS(state):
	if state == 0:
		return 0
	visited = [False] * (bitfull + 1)
	stack = [state]
	visited[state] = True
	depth = 0
	while True:
		depth += 1
		nstack = set()
		for u in stack:
			mins = getmins(u)
			for r1 in range(3):
				for r2 in range(r1 + 1, 4):
					(rfrom, rto) = (r1, r2) if mins[r1] < mins[r2] else (r2, r1)
					if mins[rfrom] > N:
						continue
					v = move(u, mins[rfrom], rto)
					if v == 0:
						return depth
					if not visited[v]:
						nstack.add(v)
						visited[v] = True
		stack = nstack
state = 0
for rod in list(map(int, input().strip().split()))[::-1]:
	state <<= 2
	state |= rod - 1
print(BFS(state))


import sys
from itertools import *
from math import *
from copy import copy, deepcopy
from collections import *
from queue import Queue
from heapq import heappush, heappop, heapify
from operator import *
from functools import reduce
from string import ascii_lowercase, ascii_uppercase
gi = lambda : int(input())
gis = lambda : list(map(int, input().split()))
gs = lambda : input()
skiplast = lambda x: range(len(x) - 1)
is_even = lambda x: x % 2 == 0
inf = float('inf')

def get_neighbors(rods):
	for i in range(4):
		if not rods[i]:
			continue
		for j in range(4):
			if j == i:
				continue
			if len(rods[j]) == 0 or rods[j][-1] > rods[i][-1]:
				yield (i, j)
n = gi()
rods = [[], [], [], []]
for (i, d) in enumerate(gis(), start=1):
	rods[d - 1].append(i)
start = tuple([tuple(sorted(rod, reverse=True)) for rod in rods])
END = (tuple(reversed(range(1, n + 1))), tuple(), tuple(), tuple())
visited = set([start])
q = deque([(start, 0)])
while q:
	(node, dist) = q.popleft()
	if node == END:
		break
	for (i, j) in get_neighbors(node):
		neighbor = [list(rod) for rod in node]
		neighbor[j].append(neighbor[i].pop())
		neighbor[1:] = sorted(neighbor[1:], key=lambda x: x[-1] if x else 0)
		neighbor = tuple((tuple(rod) for rod in neighbor))
		if neighbor not in visited:
			visited.add(neighbor)
			q.append((neighbor, dist + 1))
print(dist)


import sys
import queue
n = int(input().strip())
bases = [1]
for i in range(1, n + 1):
	bases.append(4 ** i)
a = 0
i = 0
for a_temp in input().strip().split():
	a += (int(a_temp) - 1) * bases[i]
	i += 1
visited = [False] * bases[-1]
rod = {0, 1, 2, 3}
q = []
q.append((0, a))
visited[a] = True
if a == 0:
	print(0)
	sys.exit()
sol_found = False
k = 0
cnt = 0
while not sol_found:
	stage_list = q[cnt]
	cnt += 1
	k = stage_list[0]
	stage = stage_list[1]
	occupied = set()
	next_rod = rod.copy()
	for i in range(n):
		current_rod = stage // bases[i] % 4
		if current_rod in occupied:
			continue
		occupied.add(current_rod)
		next_rod.discard(current_rod)
		plain = stage & bases[n] - 3 * bases[i] - 1
		for r in next_rod:
			new_stage = plain + r * bases[i]
			if not visited[new_stage]:
				if new_stage == 0:
					sol_found = True
					print(k + 1)
					sys.exit()
				q.append((k + 1, new_stage))
				visited[new_stage] = True


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import sys
from collections import deque
N = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]

def restored(s):
	return all([p == 0 for p in s[1:]])

def lsigbit(x):
	return x - (x & x - 1)

def next_moves(s):
	for i in range(len(s)):
		for j in range(len(s)):
			if i == j:
				continue
			f = lsigbit(s[i])
			t = lsigbit(s[j])
			if 0 < f < t or t == 0:
				t = [x for x in s]
				t[i] -= f
				t[j] += f
				yield tuple(t[:1] + sorted(t[1:]))

def search(s0):
	q = deque([(s0, 0)])
	visited = set()
	while len(q) > 0:
		(s, step) = q.popleft()
		if restored(s):
			return step
		elif s not in visited:
			visited.add(s)
			nm = set([ss for ss in next_moves(s) if ss not in visited])
			q.extend([(ss, step + 1) for ss in nm])

def encode(arr):
	s = [0] * 4
	for (i, x) in enumerate(arr):
		s[x - 1] += 1 << i
	return tuple(s)
print(search(encode(a)))


import sys
N = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]

def move1(a, c):
	(p, q) = c
	if not p in a:
		return False
	i = a.index(p)
	if q in a[:i]:
		return False
	return a[:i] + tuple([q]) + a[i + 1:]

def func(N, a):
	changes = [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]
	pool = set()
	pool.add(tuple(a))
	states = set()
	states.add(tuple(a))
	state2 = set()
	counter = 0
	while True:
		counter = counter + 1
		for s in states:
			for c in changes:
				t = move1(s, c)
				if t:
					if not t in pool:
						if all(map(lambda x: x == 1, t)):
							print(counter)
							return
						else:
							state2.add(t)
		states = set(state2)
		pool.update(state2)
		state2 = set()
func(N, a)


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


from math import *
from pprint import *
from bisect import bisect
from itertools import groupby, chain, combinations, permutations
from heapq import *
from collections import deque, Counter, defaultdict
from functools import cmp_to_key, reduce

def next_states(state):
	used = [False] * 4
	for (i, p0) in enumerate(state):
		if used[p0]:
			continue
		used[p0] = True
		for (j, usedrod) in enumerate(used):
			if usedrod:
				continue
			yield (*state[:i], j, *state[i + 1:])

def run():
	n = int(input())
	initial = (0, tuple((int(r) - 1 for r in input().split())))
	solution = tuple([0] * n)
	if initial == solution:
		print(0)
		return
	found = set()
	queue = deque()
	queue.appendleft(initial)
	found.add(initial[1])
	while queue:
		state = queue.pop()
		for next_state in next_states(state[1]):
			if next_state in found:
				continue
			if next_state == solution:
				print(state[0] + 1)
				return
			queue.appendleft((state[0] + 1, next_state))
			found.add(next_state)
	print('No solution found')
run()


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


from collections import deque

def hanoi(N, a):
	if N == 0:
		return 0
	assert N > 0
	assert N == len(a)
	start = make_state(N, a)
	dists = {start: 0}
	to_visit = deque([start])
	original = (1 << N) - 1
	while to_visit:
		here = to_visit.popleft()
		dist = dists[here]
		if here == original:
			return dist
		for there in possible_theres(here):
			if there in dists:
				continue
			to_visit.append(there)
			dists[there] = dist + 1
	assert False, 'cannot reach here'

def make_state(N, a):
	state = 0
	rods = [rod - 1 for rod in a]
	for (i, rod) in enumerate(rods):
		state |= 1 << 10 * rod + i
	return state

def possible_theres(state):
	a = state & (1 << 10) - 1
	b = state >> 10 & (1 << 10) - 1
	c = state >> 20 & (1 << 10) - 1
	d = state >> 30 & (1 << 10) - 1
	disks = [a, b, c, d]
	rel_tops0 = [lowest_bit(e) for e in (a, b, c, d)]
	rel_tops = [e if e > 0 else 1 << 10 for e in rel_tops0]
	abs_tops = [x_top << i for (x_top, i) in zip(rel_tops0, range(0, 40, 10))]
	for (i, from_top) in enumerate(rel_tops):
		for (j, to_top) in enumerate(rel_tops):
			if i == j:
				continue
			if from_top >= to_top:
				continue
			assert from_top < to_top
			shift = (j - i) * 10
			assert shift != 0
			if shift > 0:
				yield (state - abs_tops[i] + (abs_tops[i] << shift))
			else:
				yield (state - abs_tops[i] + (abs_tops[i] >> -shift))

def lowest_bit(n):
	return n & ~n + 1

def main():
	N = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	cnt = hanoi(N, a)
	print(cnt)
main()


import sys
from collections import deque
considered = {}
to_visit = deque()

def add_states(state, turn, to_visit):
	top_of_posts = [min([disc for (disc, post) in enumerate(state) if post == i] + [10]) for i in range(4)]
	delta = 1 if turn >= 0 else -1
	for (i, disc) in enumerate(top_of_posts):
		if i == -1:
			continue
		for j in range(len(top_of_posts)):
			if i != j and disc < top_of_posts[j]:
				new_state = tuple([j if d == disc else p for (d, p) in enumerate(state)])
				if new_state in considered:
					other_turn = considered[new_state]
					if turn * other_turn < 0:
						return abs(turn + delta - other_turn) - 1
				else:
					considered[new_state] = turn + delta
					to_visit.append((new_state, turn + delta))
N = int(input().strip())
state = tuple([int(a_temp) - 1 for a_temp in input().strip().split(' ')])
goal_state = tuple([0 for a in state])
to_visit.append((state, 0))
considered[state] = 0
to_visit.append((goal_state, -1))
considered[goal_state] = -1
if goal_state == state:
	print(0)
else:
	while to_visit:
		(state, turn) = to_visit.popleft()
		ret = add_states(state, turn, to_visit)
		if ret is not None:
			print(ret)
			break


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import sys
from collections import deque
maxN = 10
N = int(input().strip())
a = tuple((int(a_temp) for a_temp in input().strip().split(' ')))
done = set()

def children(cost, parent_state):
	tops = [maxN + 1] * 4
	for i in range(len(parent_state) - 1, -1, -1):
		tops[parent_state[i] - 1] = i
	result = set()
	for i in range(4):
		if tops[i] <= maxN:
			for j in range(4):
				if not i == j and tops[i] < tops[j]:
					new_state = list(parent_state)
					new_state[tops[i]] = j + 1
					if new_state[-1] == 1:
						new_state = new_state[:-1]
					new_state = tuple(new_state)
					if new_state not in done:
						done.add(new_state)
						result.add((cost + 1, new_state))
	return result

def search(start):
	while start[-1] == 1:
		start = start[:-1]
	work = deque()
	work.append((0, start))
	while work:
		parent = work.pop()
		for (cost, child_state) in children(*parent):
			if len(child_state) == 0:
				return cost
			work.appendleft((cost, child_state))
print(search(a))


import sys
from collections import deque

def state_to_tuple(state):
	return tuple([tuple(state[0])] + [tuple(rod) for rod in sorted(state[1:], key=lambda x: x[-1] if x else -1)])

def get_next(state):
	next_states = []
	for frm in range(4):
		for to in range(4):
			if state[frm] and frm != to and (not state[to] or state[to][-1] > state[frm][-1]):
				new_state = [l[:] for l in state]
				disc = new_state[frm].pop()
				new_state[to].append(disc)
				next_states.append(new_state)
	return next_states

def gena_hanoi(n, a):
	final = [list(reversed(range(n))), [], [], []]
	final_id = state_to_tuple(final)
	initial = [[], [], [], []]
	for i in reversed(range(n)):
		initial[a[i] - 1].append(i)
	initial_id = state_to_tuple(initial)
	visited = set(initial_id)
	q = deque()
	q.appendleft((initial, 0))
	while q:
		(curr, moves) = q.pop()
		next_states = get_next(curr)
		for state in next_states:
			state_id = state_to_tuple(state)
			if state_id not in visited:
				if state_id == final_id:
					return moves + 1
				visited.add(state_id)
				q.appendleft((state, moves + 1))
	return -1
N = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]
print(gena_hanoi(N, a))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import sys

def sort_pos(position):
	N_rods = len(position)
	for i in range(1, N_rods):
		for j in range(1, N_rods - 1):
			if position[j] > position[j + 1]:
				(position[j], position[j + 1]) = (position[j + 1], position[j])
from math import log2

def highest_bit(number):
	if number == 0:
		return 0
	return int(log2(number))

def smallest_bit(number):
	if number == 0:
		return -1
	number &= -number
	return int(log2(number))

def unset_bit(number, bit):
	max_bit = int(log2(number)) + 1
	number &= ~(1 << max_bit | 1 << bit)
	return number

def set_bit(number, bit):
	number |= 1 << bit
	return number

def neighbor_positions(position):
	position = list(position)
	N_rods = len(position)
	res = []
	for i in range(N_rods):
		sbi = smallest_bit(position[i])
		if sbi == -1:
			continue
		for j in range(N_rods):
			if i != j:
				if position[j] == 0 or sbi < smallest_bit(position[j]):
					new_position = position[:]
					new_position[i] = unset_bit(new_position[i], sbi)
					new_position[j] = set_bit(new_position[j], sbi)
					sort_pos(new_position)
					res.append(tuple(new_position))
	return res
from collections import deque

def bfs(first_position, last_position):
	q = deque()
	q.append(first_position)
	levels = {}
	levels[first_position] = 0
	while len(q):
		position = q.popleft()
		for next_position in neighbor_positions(position):
			if next_position == last_position:
				return levels[position] + 1
			if next_position not in levels.keys():
				levels[next_position] = levels[position] + 1
				q.append(next_position)
	print('cant find last pos')
	return -1
N = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]
last_position = [0] * 4
for (i, rod) in enumerate(a):
	last_position[rod - 1] |= 1 << i
first_position = [0] * 4
for i in range(N):
	first_position[0] |= 1 << i
sort_pos(last_position)
res = bfs(tuple(first_position), tuple(last_position))
print(res)


import sys
from collections import deque
PEGS = 'abcd'

def get_neighbors(state):
	available_pegs = set(PEGS)
	for (disc, location) in enumerate(state):
		if location not in available_pegs:
			continue
		available_pegs -= {location}
		for peg in available_pegs:
			new_state = list(state)
			new_state[disc] = peg
			yield ''.join(new_state)

def reached_goal(state):
	return set(state) == {'a'}

def bfs(start):
	visited = set()
	queue = deque([(start, 0)])
	while queue:
		(node, depth) = queue.popleft()
		if node in visited:
			continue
		visited.add(node)
		if reached_goal(node):
			return depth
		depth += 1
		for neighbor in get_neighbors(node):
			if neighbor in visited:
				continue
			queue.append((neighbor, depth))

def gena_hanoi(a):
	start = ''.join((PEGS[disc - 1] for disc in a))
	return bfs(start)

def run():
	N = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	print(gena_hanoi(a))
run()


import sys
import queue

def bfs(a, N):
	initial = [[], [], [], []]
	for i in range(len(a) - 1, -1, -1):
		initial[a[i] - 1].append(i)
	solution = [list(range(N - 1, -1, -1)), [], [], []]
	solution_encoding = get_encoding(solution)
	visited = set()
	q = queue.Queue()
	q.put((initial, 0))
	while q.qsize() > 0:
		(state, moves) = q.get()
		encoding = get_encoding(state)
		if encoding == solution_encoding:
			return moves
		for i in range(4):
			if len(state[i]) == 0:
				continue
			for j in range(4):
				if i == j:
					continue
				if len(state[j]) == 0 or state[i][-1] < state[j][-1]:
					new_list = [list(x) for x in state]
					new_list[j].append(new_list[i].pop())
					encoding = get_encoding(new_list)
					if encoding not in visited:
						visited.add(encoding)
						q.put((new_list, moves + 1))

def get_encoding(state):
	sorted_state = [state[0]] + sorted(state[1:], key=lambda x: x[-1] if len(x) > 0 else -1)
	encoding = ''
	for s in sorted_state:
		for disk in s:
			encoding += str(disk)
		encoding += '|'
	return encoding
N = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]
print(bfs(a, N))


listed = set()

def goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if len(x[j]) == 0 or x[i][-1] < x[j][-1]:
					yield (i, j)

def bfs(x):

	def tt(d):
		return tuple((tuple(t) for t in d))

	def move(node, m):
		y = [list(t) for t in node]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tt(y)
	start = (tt(x), 0)
	q = [start]
	while q:
		(u, depth) = q.pop(0)
		if goal(u):
			return depth
		for x in moves(u):
			cal = move(u, x)
			if cal not in listed:
				q.append((cal, depth + 1))
				listed.add(cal)
n = int(input())
a = [int(x) for x in input().split()]
g = [[] for x in range(4)]
for x in range(0, n):
	g[a[x] - 1] = [x + 1] + g[a[x] - 1]
print(bfs(g))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
n = int(input())
a = [[] for i in range(4)]
r = [int(t) for t in input().split()]
for i in range(n):
	a[r[i] - 1] = [i + 1] + a[r[i] - 1]
print(bfs(a))


import math
import os
import random
import re
import sys

def search(pos, n):
	if pos == 0:
		return 0
	a = [False] * (1 << 2 * n)
	a[pos] = True
	q = {pos}
	d = 0
	while q:
		qq = set()
		for pos in q:
			mask = 3
			i1 = pos & mask
			for i in range(4):
				if i != i1:
					y = pos & ~mask | i
					if y == 0:
						return d + 1
					if not a[y]:
						a[y] = True
						qq.add(y)
			for j in range(1, n):
				mask = 3 << 2 * j
				i2 = (pos & mask) >> 2 * j
				if i2 != i1:
					for i in range(4):
						if i != i1 and i != i2:
							y = pos & ~mask | i << 2 * j
							if y == 0:
								return d + 1
							if not a[y]:
								a[y] = True
								qq.add(y)
					for k in range(j + 1, n):
						mask = 3 << 2 * k
						i3 = (pos & mask) >> 2 * k
						if i3 != i1 and i3 != i2:
							y = pos & ~mask | 6 - i1 - i2 - i3 << 2 * k
							if y == 0:
								return d + 1
							if not a[y]:
								a[y] = True
								qq.add(y)
							break
					break
		q = qq
		d += 1
	return -1
N = int(input())
a = list(map(int, input().rstrip().split()))
a = sum((int(x) - 1 << 2 * y for (y, x) in enumerate(a)))
print(search(a, N))


import math
import os
import random
import re
import sys

def genNextPositions(a):
	a = list(a)
	moves = {1, 2, 3, 4}
	for i in range(len(a)):
		if a[i] in moves:
			moves.remove(a[i])
			n = a[i]
			for m in moves:
				a[i] = m
				yield tuple(a)
			a[i] = n

def solve(a):
	a = tuple(a)
	end = tuple([1] * len(a))
	(stack, index) = ([(0, a)], 0)
	seenStates = {a}
	while stack:
		(count, state) = stack[index]
		index += 1
		if state == end:
			return count
		for nextState in genNextPositions(state):
			if nextState not in seenStates:
				seenStates.add(nextState)
				stack.append((count + 1, nextState))
N = int(input())
a = list(map(int, input().rstrip().split()))
print(solve(a))


import math
import os
import random
import re
import sys
from collections import deque
done_state = None

def next_comb(comb):
	for i in range(len(comb)):
		if comb[i] != '':
			for j in range(len(comb)):
				if i == j:
					continue
				if comb[j] == '' or int(comb[j][0]) > int(comb[i][0]):
					new_comb = comb[:]
					new_comb[i] = comb[i][1:]
					new_comb[j] = comb[i][0] + comb[j]
					new_comb[1:] = sorted(new_comb[1:], key=lambda x: int(x[0]) if len(x) > 0 else -1)
					yield new_comb

def is_done(comb):
	if comb[0] == done_state and ''.join(comb[1:]) == '':
		return True
	return False

def bfs(init_combin):
	queue = deque([[init_combin, 0]])
	visited_combins = set()
	visited_combins.add(' '.join(init_combin))
	while len(queue) > 0:
		node = queue.popleft()
		cur_combin = node[0]
		steps = node[1] + 1
		for new_combin in next_comb(cur_combin):
			if ' '.join(new_combin) in visited_combins:
				continue
			if is_done(new_combin):
				return steps
			visited_combins.add(' '.join(new_combin))
			queue.append([new_combin, steps])
	return -1
N = int(input())
done_state = ''.join(map(str, range(N)))
a = list(map(int, input().rstrip().split()))
init_combination = ['' for _ in range(4)]
for (disc_size, hanoi_index) in enumerate(a):
	init_combination[hanoi_index - 1] += str(disc_size)
print(bfs(init_combination))


import math
import os
import random
import re
import sys
N = int(input())
a = list(map(int, input().rstrip().split()))

def tuplify(aa):
	return tuple((tuple(a) for a in aa))

def is_target(node):
	for i in range(1, 4):
		if node[i]:
			return False
	return True

def allowed(state):
	all_moves = [(i, j) for i in range(len(state)) for j in range(len(state))]
	moves = []
	for (s0, s1) in all_moves:
		if len(state[s0]) == 0:
			continue
		if not state[s1] or state[s0][-1] < state[s1][-1]:
			moves.append((s0, s1))
	return moves

def rearrange(node, move):
	state = [list(s) for s in node]
	state[move[1]].append(state[move[0]].pop())
	state[1:4] = sorted(state[1:4], key=lambda x: x[-1] if x else 0)
	return tuplify(state)

def bfs(init):
	from collections import deque
	num_steps = 0
	nextSteps = deque([(tuplify(init), num_steps)])
	visited = set()
	while nextSteps:
		(node, num_steps) = nextSteps.popleft()
		if is_target(node):
			return num_steps
		if node in visited:
			continue
		visited.add(node)
		for m in allowed(node):
			n = rearrange(node, m)
			if n not in visited:
				nextSteps.append((n, num_steps + 1))
	return 'impossible!'
init = [[] for i in range(4)]
for (d, stack) in enumerate(a):
	init[stack - 1] = [d] + init[stack - 1]
steps = bfs(init)
print(steps)


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(tuplify(x))
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys

def get_all_neighbors(nd):
	global parents
	nds = nd.split('_')
	node = list(map(lambda x: int(x), nds))
	n = len(node)
	nn = n
	poles = {1: 11, 2: 11, 3: 11, 4: 11}
	for i in range(n, 0, -1):
		poles[node[i - 1]] = i
	vals = list(zip(poles.keys(), poles.values()))
	vals.sort(key=lambda x: x[1])
	nbrs = []
	for i in range(0, 3):
		if vals[i][1] > 10:
			break
		for j in range(3, i, -1):
			tnode = [dsk for dsk in node]
			tnode[vals[i][1] - 1] = vals[j][0]
			if tnode[-1] == 1:
				tnode.pop()
				if nn == n:
					nn = n - 1
					nbrs = []
			if len(tnode) == nn:
				tn = '_'.join(map(str, tnode))
				if tn not in parents:
					parents[tn] = nd
					nbrs.append((tn, nn))
					parents[tn.replace('3', '5').replace('2', '3').replace('5', '2')] = nd
					parents[tn.replace('4', '5').replace('2', '4').replace('5', '2')] = nd
					parents[tn.replace('4', '5').replace('3', '4').replace('5', '3')] = nd
	if n > nn:
		return (nbrs, True)
	else:
		return (nbrs, False)

def solution(a):
	global parents
	while a[-1] == 1:
		a.pop()
		if not a:
			return 0
	n = len(a)
	min_length = n
	cut_length = False
	start_state = '_'.join([str(i) for i in a])
	end_state = ''
	parents = {start_state: None}
	q = [(start_state, n, 0)]
	(nxt, length, level) = q.pop(0)
	while True:
		(nbrs, cut) = get_all_neighbors(nxt)
		if cut:
			cut_length = True
		q += list(map(lambda x: (x[0], x[1], level + 1), nbrs))
		if end_state in parents:
			return level + 1
		if q:
			(nxt, length, tlevel) = q.pop(0)
			if tlevel > level:
				min_length = min_length - int(cut_length)
				cut_length = False
				level = tlevel
		else:
			return -1
N = int(input())
a = list(map(int, input().rstrip().split()))
res = solution(a)
print(res)


from collections import deque

def serialize(a):
	l = [tuple(t) for t in a]
	l[1:] = sorted(l[1:])
	return tuple(l)

def deserialize(a):
	return deque([deque(t) for t in a])

def copy(a):
	return deque([deque(t) for t in a])

def helper(n, aa):
	a = [deque() for _ in range(4)]
	for (i, v) in enumerate(aa):
		a[v - 1].append(i + 1)
	step = 1
	(q, qq) = ([a], [])
	vis = set()
	vis.add(serialize(a))
	target = serialize([deque(range(1, n + 1)), deque(), deque(), deque()])
	while q:
		while q:
			a = q.pop()
			for i in range(4):
				for j in range(4):
					if a[i] and (not a[j] or a[i][0] < a[j][0]):
						a2 = copy(a)
						a2[j].appendleft(a2[i].popleft())
						a3 = serialize(a2)
						if a3 == target:
							return step
						if a3 in vis:
							continue
						vis.add(a3)
						qq.append(a2)
		(q, qq) = (qq, q)
		step += 1
N = int(input())
a = list(map(int, input().rstrip().split()))
print(helper(N, a))


import math
import os
import random
import re
import sys
from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys

def BFS(state):
	state = tuple([x - 1 for x in state])
	numDiscs = len(state)
	target = (0,) * numDiscs
	processing = set()
	processing.add(state)
	used = set()
	if state == target:
		return 0
	steps = 1
	while processing:
		nextShell = set()
		for state in processing:
			used.add(state)
			for neighbour in getNeighbours(state, numDiscs):
				if not neighbour in used and neighbour not in processing and (neighbour not in nextShell):
					if neighbour == target:
						return steps
					nextShell.add(neighbour)
		steps += 1
		processing = nextShell

def getNeighbours(state, numDiscs):
	topPegs = [numDiscs] * 4
	for disc in range(numDiscs):
		peg = state[disc]
		topPegs[peg] = min(topPegs[peg], disc)
	neighbours = []
	for peg1 in range(4):
		for peg2 in range(peg1 + 1, 4):
			disc1 = topPegs[peg1]
			disc2 = topPegs[peg2]
			if disc2 < disc1:
				neighbours.append(state[:disc2] + (peg1,) + state[disc2 + 1:])
			if disc1 < disc2:
				neighbours.append(state[:disc1] + (peg2,) + state[disc1 + 1:])
				pass
	return neighbours
N = int(input())
a = list(map(int, input().rstrip().split()))
print(BFS(a))


def bfs(start, num):

	def move(data):
		res_temp = [11, 11, 11, 11]
		res = []
		data_temp = data
		for i in range(1, num + 1):
			temp = data_temp % 4
			data_temp >>= 2
			if res_temp[temp] == 11:
				res_temp[temp] = i
		for i in range(4):
			for j in range(i + 1, 4):
				if res_temp[i] < res_temp[j]:
					bit = (res_temp[i] - 1) * 2
					num_temp = num_max - (3 << bit)
					res.append(data & num_temp | j << bit)
				elif res_temp[i] > res_temp[j]:
					bit = (res_temp[j] - 1) * 2
					num_temp = num_max - (3 << bit)
					res.append(data & num_temp | i << bit)
				else:
					pass
		return res
	res = 0
	num_max = 4 ** num - 1
	stat_noted = (num_max + 1) * [0]
	stat_noted[start] = 1
	temp = [start]
	while True:
		res += 1
		tetemp = []
		for i in temp:
			res_step = move(i)
			for j in res_step:
				if j == 0:
					return res
				if stat_noted[j] == 0:
					stat_noted[j] = 1
					tetemp.append(j)
		temp = tetemp
num = int(input().strip())
cache_rod = list(map(int, input().strip().split()))
start = 0
for i in range(num):
	start += cache_rod[i] - 1 << 2 * i
print(bfs(start, num))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys
from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


n = int(input())
s = ''.join(input().split())
assert len(s) == n and min(s) >= '1' and (max(s) <= '4')

def neighbors(u):
	available = set('1234')
	for i in range(n):
		if u[i] in available:
			available.remove(u[i])
			for a in available:
				yield (u[:i] + a + u[i + 1:])
			if len(available) <= 1:
				break
from collections import deque
(t, q, dist) = ('1' * n, deque([s]), {s: 0})
while t not in dist:
	u = q.popleft()
	for v in neighbors(u):
		if v not in dist:
			dist[v] = dist[u] + 1
			q.append(v)
print(dist[t])


import math
import os
import random
import re
import sys
import heapq

def est(state, n):
	l = len(state[0])
	if l == n:
		return 0
	for k in range(n):
		val = n - 1 - k
		if l <= k:
			result = 0
			break
		if state[0][::-1][k] != val:
			result = l - k
			break
	for t in range(1, 4):
		for (j, v) in enumerate(state[t]):
			if v == val:
				return result + j + val + 1

def move(state, from_, to):
	new_state = []
	for i in range(4):
		if i == from_:
			new_state.append(state[i][1:])
		elif i == to:
			new_state.append((state[from_][0],) + state[i])
		else:
			new_state.append(state[i])
	k1 = new_state[1][-1] if new_state[1] else -1
	v1 = new_state[1]
	k2 = new_state[2][-1] if new_state[2] else -1
	v2 = new_state[2]
	k3 = new_state[3][-1] if new_state[3] else -1
	v3 = new_state[3]
	if k2 < k1:
		(k1, k2) = (k2, k1)
		(v1, v2) = (v2, v1)
	if k3 < k1:
		(k1, k3) = (k3, k1)
		(v1, v3) = (v3, v1)
	if k3 < k2:
		(k2, k3) = (k3, k2)
		(v2, v3) = (v3, v2)
	return (new_state[0], v1, v2, v3)

def moves(state):
	for i in range(4):
		if not state[i]:
			continue
		for j in range(4):
			if i == j:
				continue
			if not state[j]:
				if len(state[i]) == 1 and 0 not in (i, j):
					continue
			if not state[j] or state[i][0] < state[j][0]:
				yield move(state, i, j)

def hanoi(state):
	n = sum((len(t) for t in state))
	queue = [(est(state, n), 0, state)]
	seen = {}
	while queue:
		(curr_est, cost, state) = heapq.heappop(queue)
		if len(state[0]) == n:
			return cost
		for move in moves(state):
			extra_cost = est(move, n)
			updated_est = cost + extra_cost
			if seen.get(move, 1 + updated_est) <= updated_est:
				continue
			seen[move] = updated_est
			heapq.heappush(queue, (cost + extra_cost, 1 + cost, move))
N = int(input())
a = list(map(int, input().rstrip().split()))
state = [[] for i in range(4)]
for (i, tower) in enumerate(a):
	state[tower - 1].append(i)
state = tuple((tuple(tower) for tower in state))
print(hanoi(state))


import math
import os
import random
import re
import sys
from collections import deque
from copy import copy

def solve(a):
	n = len(a)
	states = [-1 for _ in range(4 ** n)]

	def get_state(a):
		p = 1
		s = 0
		for x in a:
			s += (x - 1) * p
			p *= 4
		return s
	start = [1] * n
	finish = get_state(a)
	start_state = get_state(start)
	states[start_state] = 0
	q = deque()
	q.append((start_state, start))
	while len(q) > 0:
		(s, arr) = q.popleft()
		if s == finish:
			return states[finish]
		bag = set()
		for (disc, i) in zip(arr, range(n)):
			if disc in bag:
				continue
			bag.add(disc)
			for rod in range(1, 5):
				if rod in bag:
					continue
				arr[i] = rod
				state = get_state(arr)
				if states[state] == -1:
					q.append((state, copy(arr)))
					states[state] = states[s] + 1
			arr[i] = disc
	return -1
N = int(input())
a = list(map(int, input().rstrip().split()))
s = solve(a)
print(s)


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys
from collections import deque

def isfinal(state):
	for rod in state:
		if rod != 1:
			return False
	return True

def find(state, n):
	if isfinal(state):
		return 0
	seenstates = set()
	queue = deque([(state, 0)])
	while len(queue) > 0:
		(state, step) = queue.popleft()
		seenrods = set()
		for (disc, rod) in enumerate(state):
			if rod not in seenrods:
				seenrods.add(rod)
				for nextrod in range(1, 5):
					if nextrod not in seenrods:
						newstate = state.copy()
						newstate[disc] = nextrod
						if isfinal(newstate):
							return step + 1
						if tuple(newstate) not in seenstates:
							seenstates.add(tuple(newstate))
							queue.append((newstate, step + 1))
n = int(input())
a = list(map(int, input().rstrip().split()))
print(find(a, n))


import math
import os
import random
import re
import sys
from collections import deque

def isSolved(l):
	return all([len(l[i]) == 0 for i in range(1, len(l))])

def tuplify(l):
	return tuple((tuple(i) for i in l))

def possibleMoves(l):
	for i in range(len(l)):
		if l[i]:
			for j in range(len(l)):
				if not l[j] or l[i][-1] < l[j][-1]:
					yield (i, j)

def move(x, y):
	temp = [list(i) for i in x]
	temp[y[1]].append(temp[y[0]].pop())
	temp[1:4] = sorted(temp[1:4], key=lambda t: t[-1] if t else 0)
	return tuplify(temp)

def BFS(l):
	visited = set()
	start = (tuplify(l), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, d) = q.popleft()
		if isSolved(node):
			return d
		for i in possibleMoves(node):
			child = move(node, i)
			if child not in visited:
				visited.add(child)
				q.append((child, d + 1))
N = int(input())
a = list(map(int, input().rstrip().split()))
l = [[] for i in range(4)]
for i in range(N):
	l[a[i] - 1] = [i + 1] + l[a[i] - 1]
print(BFS(l))


import collections
import io
import os
import sys

def hanoi_3(n):
	return (1 << n) - 1
hanoi_4_memo = {0: 0, 1: 1, 2: 3, 3: 5}

def hanoi_4(n):
	if n in hanoi_4_memo:
		return hanoi_4_memo[n]
	if n < 0:
		return None
	result = min((hanoi_4(k) * 2 + hanoi_3(n - k) for k in range(1, n)))
	hanoi_4_memo[n] = result
	return result

def legal_moves(config):
	tops = [config.index(p) + 1 if p in config else 0 for p in range(1, 5)]
	for (i, p1) in enumerate(tops):
		if p1 != 0:
			for (j, p2) in enumerate(tops):
				if i != j and (p2 == 0 or p2 > p1):
					yield (i + 1, j + 1, p1)

def moves(c):
	return list(legal_moves(c))

def create_peg_top(c):
	return [c.index(p) + 1 if p in c else 0 for p in range(1, 5)]

def h4solve(c_target):
	global bfs, config, depth, cseen, goal
	goal = tuple(c_target)
	n = len(goal)
	if not all((1 <= p <= 4 for p in goal)):
		return None
	config = (1,) * n
	if config == goal:
		return 0
	cseen = {config: 0}
	bfs = collections.deque([(0, config)])
	while len(bfs) > 0:
		(depth, config) = bfs.popleft()
		depth = depth + 1
		for (p1, p2, d) in legal_moves(config):
			new_cfg = config[:d - 1] + (p2,) + config[d:]
			if new_cfg not in cseen:
				if new_cfg == goal:
					return depth
				cseen[new_cfg] = depth
				bfs.append((depth, new_cfg))
	return None
N = int(input())
a = list(map(int, input().rstrip().split()))
result = h4solve(a)
print(result)


import math
import os
import random
import re
import sys
from collections import deque

def hanoi4(a):
	n = len(a)

	def adjs(state):
		builder = decode(state)
		for (i, tower1) in enumerate(builder):
			if not tower1:
				continue
			disc = tower1.pop()
			for (j, tower2) in enumerate(builder):
				if not tower2 or disc < tower2[-1]:
					tower2.append(disc)
					yield encode(builder)
					tower2.pop()
			tower1.append(disc)

	def encode(builder):
		return tuple(map(tuple, builder[0:1] + sorted(builder[1:4], key=tower_key)))

	def decode(state):
		return list(map(list, state))
	tower_key = lambda tower: tower[-1] if tower else 10
	builder0 = [[] for _ in range(4)]
	for disc in reversed(range(n)):
		builder0[a[disc] - 1].append(disc)
	state0 = encode(builder0)
	queue = deque([(state0, 0)])
	seen = set()
	while queue:
		(state, moves) = queue.popleft()
		if state in seen:
			continue
		if len(state[0]) == n:
			return moves
		seen.add(state)
		queue.extend(((adj, moves + 1) for adj in adjs(state)))
N = int(input())
a = list(map(int, input().rstrip().split()))
result = hanoi4(a)
print(result)


import math
import os
import random
import re
import sys
from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys
from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys
from collections import deque

def steps_mhanoy(tower):
	l = len(tower)
	steps = 0
	state = 0
	win = 0

	def move(rod, disc):
		nonlocal state
		disc *= 2
		state &= ~(3 << disc)
		state |= rod << disc

	def iterate_state():
		st = state
		for i in range(l):
			yield (3 & st)
			st >>= 2

	def print_state():
		print(' '.join(['{}'.format(i) for i in iterate_state()]) + ' _ {}'.format(steps))

	def print_rods():
		rods = [[] for _ in range(4)]
		j = 0
		print('depth: {}'.format(steps))
		for i in iterate_state():
			rods[i].append(str(j))
			j += 1
		for i in rods:
			print('| ' + ' '.join(reversed(i)))

	def get_disc_rod(disc):
		return 3 & state >> 2 * disc

	def get_rod_top(rod):
		st = state
		for i in range(l):
			r = 3 & st
			if r == rod:
				return i
			st >>= 2
		return l

	def get_rod_base(rod):
		st = state
		ret = l
		for i in range(l):
			r = 3 & st
			if r == rod:
				ret = i
			st >>= 2
		return ret
	for i in range(l):
		move(tower[i] - 1, i)
	if state == win:
		return 0
	start = state
	bfs = deque()
	bfs.append(state)
	depth = dict()
	depth[state] = 0
	while len(bfs):
		cstate = state = bfs.popleft()
		steps = depth[state]
		d = [get_rod_top(r) for r in range(4)]
		for fro in range(4):
			if d[fro] == l:
				continue
			for to in range(4):
				if d[to] > d[fro]:
					state = cstate
					move(to, d[fro])
					if state == win:
						return steps + 1
					if state not in depth and state != start:
						depth[state] = steps + 1
						bfs.append(state)
	return depth[0]
N = int(input())
a = list(map(int, input().rstrip().split()))
s = steps_mhanoy(a)
print('{}'.format(s))


import math
import os
import random
import re
import sys
from collections import deque

def tuplify(x):
	return tuple((tuple(t) for t in x))

def listify(x):
	return list((list(t) for t in x))

def legalmoves(towers):
	for i in range(len(towers)):
		if towers[i]:
			for j in range(len(towers)):
				if not towers[j] or towers[i][-1] < towers[j][-1]:
					yield (i, j)

def movetop(towers, fromtower, totower):
	towers = [[t for t in T] for T in towers]
	towers[totower].append(towers[fromtower].pop())
	towers[1:] = sorted(towers[1:], key=lambda t: t[-1] if t else 0)
	return towers

def goal(towers):
	lent = [len(t) for t in towers]
	lent = [t == 0 for t in lent[1:]]
	return all(lent)

def hanoi(N, a):
	towers = [[] for i in range(4)]
	for i in range(N):
		towers[a[N - i - 1] - 1].append(N - i)
	bfs = deque()
	bfs.append((tuplify(towers), 0))
	visited = set()
	visited.add(tuplify(towers))
	while bfs:
		(node, depth) = bfs.popleft()
		node = listify(node)
		if goal(node):
			return depth
		for move in legalmoves(node):
			child = movetop(node, move[0], move[1])
			child = tuplify(child)
			if not child in visited:
				visited.add(child)
				bfs.append((child, depth + 1))
N = int(input())
a = list(map(int, input().rstrip().split()))
print(hanoi(N, a))


import math
import os
import random
import re
import sys
from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys
from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
R = list(map(int, input().rstrip().split()))
A = [[] for i in range(4)]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


def generate(move, N):
	(next, i) = ([], 0)
	available = [1, 2, 3, 4]
	while i < N:
		if len(available) == 0:
			break
		elif move[i] in available:
			available.remove(move[i])
		else:
			i = i + 1
			continue
		for m in available:
			amove = list(move)
			amove[i] = m
			next.append(tuple(amove))
		i = i + 1
	return set(next)
N = int(input())
a = list(map(int, input().split()))
(initial, i) = ([], 0)
while i < N:
	initial.append(1)
	i = i + 1
moves = set([tuple(initial)])
current = set(moves)
gen = 0
while True:
	next = set()
	for move in current:
		next.update(generate(move, N))
	gen += 1
	next.difference_update(moves)
	moves.update(next)
	if tuple(a) in next:
		print(gen)
		break
	current = set(next)


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys
from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
a = list(map(int, input().rstrip().split()))
discs = [[] for _ in range(4)]
for i in range(N):
	discs[a[i] - 1].append(i + 1)
discs = [x[::-1] for x in discs]
print(bfs(discs))


import math
import os
import random
import re
import sys
from collections import deque

def hanoi(start, goal):
	distances = {start: 0}
	queue = deque([start])
	while queue:
		a = queue.popleft()
		d = distances[a]
		if a == goal:
			return d
		for neighbour in neighbours(a):
			if neighbour not in distances:
				queue.append(neighbour)
				distances[neighbour] = d + 1

def top_of_pole(a, p):
	for (i, x) in enumerate(a):
		if x == p:
			return i
	return -1

def replace_in_tuple(a, i, x):
	return a[:i] + (x,) + a[i + 1:]

def neighbours(a):
	tops = {i: top_of_pole(a, i) for i in range(1, 5)}
	out = []
	for i in tops:
		if tops[i] == -1:
			continue
		for j in tops:
			if tops[j] == -1 or tops[i] < tops[j]:
				out.append(replace_in_tuple(a, tops[i], j))
	return out
n = int(input())
start = tuple(map(int, input().rstrip().split()))
goal = (1,) * n
print(hanoi(start, goal))


import math
import os
import random
import re
import sys
from itertools import permutations
import queue
history = set()

def to_tuple(d):
	return tuple((tuple(x) for x in [d[0]] + sorted(d[1:])))

def valid(d, i, j):
	if len(d[i]) == 0:
		return False
	if len(d[j]) == 0:
		return True
	return d[i][-1] < d[j][-1]

def success(d):
	return all((len(x) == 0 for x in d[1:]))

def move(d, i, j):
	d[j].append(d[i].pop())
	return d

def get_min_steps(q):
	n = 0
	while q:
		d = q.pop(0)
		if type(d) == int:
			n = d
			q.append(d + 1)
			d = q.pop(0)
		if success(d):
			return n
		for (i, j) in permutations(range(4), 2):
			if not valid(d, i, j):
				continue
			d_ = [x[:] for x in d]
			d_ = move(d_, i, j)
			t = to_tuple(d_)
			if t in history:
				continue
			history.add(t)
			q.append(d_)
	return None
N = int(input())
a = list(map(int, input().rstrip().split()))
d = [[], [], [], []]
for (i, x) in enumerate(a):
	d[x - 1].append(i)
d = [sorted(x, reverse=True) for x in d]
history.add(to_tuple(d))
q = [d, 1]
print(get_min_steps(q))


N = 4
n = int(input())
a = tuple(map(lambda x: int(x) - 1, input().split()))

def next_states(state):
	has = [False] * N
	for (i, v) in enumerate(state):
		if has[v]:
			continue
		has[v] = True
		for j in range(N):
			if not has[j]:
				yield (state[:i] + (j,) + state[i + 1:])

def search(start, goal):
	if start == goal:
		return 0
	current = [start]
	visited = {start}
	moves = 1
	while current:
		neighbors = []
		for state in current:
			for neighbor in next_states(state):
				if neighbor == goal:
					return moves
				if neighbor not in visited:
					visited.add(neighbor)
					neighbors.append(neighbor)
		moves += 1
		current = neighbors
	return -1
print(search(a, (0,) * n))


import math
import os
import random
import re
import sys
import queue

def rod_top(rod_bitset):
	i = 0
	while i < 10:
		if rod_bitset & 1 << i != 0:
			return i
		i += 1
	return -1

def get_stack_from_input(N, a):
	rods = [0, 0, 0, 0]
	for (diameter, rodindex) in reversed(list(enumerate(a))):
		rods[rodindex - 1] |= 1 << diameter
	return tuple([(r, rod_top(r)) for r in rods])

def is_beginning_state(rods, N):
	return rods[0][0] == (1 << N) - 1

def hash_stack(rods):
	l = sorted([rods[1][0], rods[2][0], rods[3][0]])
	return rods[0][0] << 30 | l[0] << 20 | l[1] << 10 | l[2]

def can_place(rods, rfrom, rto):
	return rods[rfrom][1] >= 0 and (rods[rto][1] == -1 or rods[rfrom][1] < rods[rto][1])

def setbit(n, i):
	return n | 1 << i

def clearbit(n, i):
	return ~setbit(~n, i)

def place_and_get_stack(rods, rfrom, rto):
	(oldFrom, oldTopFrom) = rods[rfrom]
	(oldTo, oldTopTo) = rods[rto]
	newFrom = clearbit(oldFrom, oldTopFrom)
	newTopFrom = oldTopFrom + 1
	while newTopFrom < 10:
		if newFrom & 1 << newTopFrom != 0:
			break
		newTopFrom += 1
	if newTopFrom == 10:
		newTopFrom = -1
	newTopTo = oldTopFrom
	newTo = setbit(oldTo, newTopTo)
	stack = []
	for i in range(4):
		if i == rfrom:
			stack.append((newFrom, newTopFrom))
		elif i == rto:
			stack.append((newTo, newTopTo))
		else:
			stack.append(rods[i])
	return stack

def adj_stacks(rods):
	adj = []
	for i in range(4):
		for j in range(4):
			if i == j:
				continue
			if can_place(rods, i, j):
				adj.append(place_and_get_stack(rods, i, j))
	return adj

def solve(N, a):
	init_rods = get_stack_from_input(N, a)
	seen = set()
	q = queue.Queue()
	q.put((init_rods, 0))
	while q.qsize() > 0:
		(rods, moves) = q.get()
		my_hash = hash_stack(rods)
		if my_hash in seen:
			continue
		seen.add(hash_stack(rods))
		if is_beginning_state(rods, N):
			return moves
		for adj in adj_stacks(rods):
			q.put((adj, moves + 1))
	return -1
N = int(input())
a = list(map(int, input().rstrip().split()))
print(solve(N, a))


import math
import os
import random
import re
import sys
import copy
from collections import deque

def tuplify(x):
	return tuple((tuple(t) for t in x))

def legalMove(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def doMove(p, m):
	lst = [list(t) for t in p]
	lst[m[1]].append(lst[m[0]].pop())
	lst[1:4] = sorted(lst[1:4], key=lambda t: t[-1] if t else 0)
	return tuplify(lst)

def goal(x):
	return all([len(x[i]) == 0 for i in range(1, 4)])

def bfs(s):
	visited = set()
	search_queue = deque([(tuplify(s), 0)])
	while search_queue:
		(node, depth) = search_queue.popleft()
		if goal(node):
			return depth
		for move in legalMove(node):
			child = doMove(node, move)
			if not child in visited:
				visited.add(child)
				search_queue.append((child, depth + 1))
N = int(input())
a = list(map(int, input().rstrip().split()))
s = [[] for _ in range(4)]
for i in range(1, len(a) + 1):
	s[a[-i] - 1].append(len(a) + 1 - i)
print(bfs(s), end='')


import math
import os
import random
import re
import sys
from collections import deque

def moves(rods):
	for i in range(len(rods)):
		if rods[i]:
			for j in range(len(rods)):
				if not rods[j] or rods[i][-1] < rods[j][-1]:
					yield (i, j)

def move(rods, m):
	rods = [list(x) for x in rods]
	rods[m[1]].append(rods[m[0]].pop())
	rods[1:4] = sorted(rods[1:4], key=lambda x: x[-1] if x else 0)
	return tuple((tuple(x) for x in rods))

def hanoi(rods):
	visited = set()
	start = (rods, 0)
	queue = deque([start])
	visited.add(start)
	while queue:
		(node, depth) = queue.popleft()
		if all([len(node[i]) == 0 for i in range(1, len(node))]):
			return depth
		for m in moves(node):
			child = move(node, m)
			if child not in visited:
				visited.add(child)
				queue.append((child, depth + 1))
N = int(input())
rods = [[] for i in range(4)]
a = list(map(int, input().rstrip().split()))
for i in range(len(a)):
	rods[a[i] - 1] = [i + 1] + rods[a[i] - 1]
rods = tuple((tuple(x) for x in rods))
print(hanoi(rods))


from itertools import product
from itertools import product
P = [*product(range(4), repeat=2)]

def gen_moves(arrangement, n):
	tops = [-1] * 4
	arr = arrangement
	for j in range(n):
		tops[arr % 4] = j
		arr //= 4
	for (i, j) in P:
		if tops[i] > tops[j]:
			yield (arrangement + 4 ** tops[i] * (j - i))

def distances(N):
	curr = 0
	distance = {curr: 0}
	frontier = {curr}
	while frontier:
		nF = set()
		for x in frontier:
			for y in gen_moves(x, N):
				if y not in distance:
					distance[y] = distance[x] + 1
					nF.add(y)
		frontier = nF
	return distance
N = int(input())
a = tuple(map(lambda x: int(x) - 1, input().rstrip().split()))
D = distances(N)
q = sum((4 ** (N - n - 1) * x for (n, x) in enumerate(a)))
print(D[q])


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys
from collections import deque

def steps_mhanoy(a):
	l = len(a)
	rangel = range(l)
	steps = 0
	state = 0
	win = 0

	def move(rod, disc):
		nonlocal state
		disc *= 2
		state &= ~(3 << disc)
		state |= rod << disc

	def get_rod_top(rod):
		st = state
		for i in rangel:
			r = 3 & st
			if r == rod:
				return i
			st >>= 2
		return l
	for i in rangel:
		move(a[i] - 1, i)
	if state == win:
		return 0
	bfs = deque()
	bfs.append(state)
	depth = dict()
	depth[state] = 0
	range4 = range(4)
	while True:
		cstate = state = bfs.popleft()
		steps = depth[state]
		d = [get_rod_top(r) for r in range4]
		for fro in range4:
			if d[fro] == l:
				continue
			for to in range4:
				if d[to] > d[fro]:
					state = cstate
					move(to, d[fro])
					if state == win:
						return steps + 1
					if state not in depth:
						depth[state] = steps + 1
						bfs.append(state)
	return depth[0]
N = int(input())
a = list(map(int, input().rstrip().split()))
print(steps_mhanoy(a))


from collections import deque

def serialize(a):
	l = [tuple(t) for t in a]
	l[1:] = sorted(l[1:])
	return tuple(l)

def deserialize(a):
	return deque([deque(t) for t in a])

def copy(a):
	return deque([deque(t) for t in a])

def helper(n, aa):
	a = [deque() for _ in range(4)]
	for (i, v) in enumerate(aa):
		a[v - 1].append(i + 1)
	step = 1
	(q, qq) = ([a], [])
	vis = set()
	vis.add(serialize(a))
	target = serialize([deque(range(1, n + 1)), deque(), deque(), deque()])
	while q:
		while q:
			a = q.pop()
			for i in range(4):
				for j in range(4):
					if a[i] and (not a[j] or a[i][0] < a[j][0]):
						a2 = copy(a)
						a2[j].appendleft(a2[i].popleft())
						a3 = serialize(a2)
						if a3 == target:
							return step
						if a3 in vis:
							continue
						vis.add(a3)
						qq.append(a2)
		(q, qq) = (qq, q)
		step += 1
N = int(input())
a = list(map(int, input().rstrip().split()))
print(helper(N, a))


import math
import os
import random
import re
import sys

def main():
	N = int(input())
	a = list(map(int, input().rstrip().split()))
	arr = [0 for _ in range(4)]
	for (val, ind) in enumerate(a, 1):
		arr[ind - 1] += 2 ** (val - 1)
	seen = {}
	seen[tuple(arr)] = 1
	currStack = [tuple(arr)]
	steps = 0
	while True:
		newStack = []
		nextMoves = []
		for nele in currStack:
			for i in range(0, 4):
				for j in range(i + 1, 4):
					li = nele[i] & -nele[i]
					lj = nele[j] & -nele[j]
					ele = list(nele)
					if li > lj and lj != 0 or li == 0:
						ele[j] -= lj
						ele[i] += lj
					elif li != 0:
						ele[i] -= li
						ele[j] += li
					ele = tuple(ele)
					nextMoves.append(ele)
		steps += 1
		for ele in nextMoves:
			if ele not in seen:
				newStack.append(ele)
				seen[ele] = 1
				if ele[1] + ele[2] + ele[3] == 0:
					print(steps)
					return
		currStack = newStack
main()


import sys

def generate(move, N):
	next = []
	i = 0
	available = [1, 2, 3, 4]
	while i < N:
		if len(available) == 0:
			break
		elif move[i] in available:
			available.remove(move[i])
		else:
			i = i + 1
			continue
		for m in available:
			amove = list(move)
			amove[i] = m
			next.append(tuple(amove))
		i = i + 1
	return set(next)
N = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]
initial = []
i = 0
while i < N:
	initial.append(1)
	i = i + 1
moves = set()
moves.add(tuple(initial))
current = set(moves)
gen = 0
while True:
	next = set()
	for move in current:
		next.update(generate(move, N))
	gen = gen + 1
	next.difference_update(moves)
	moves.update(next)
	if tuple(a) in next:
		print(gen)
		break
	current = set(next)


import math
import os
import random
import re
import sys
from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys
from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys

def Hanoi(a):
	visited = {''.join(map(str, a))}
	target = '1' * N
	fromStat = {''.join(map(str, a))}
	ans = 0
	while True:
		if target in fromStat:
			return ans
		toStat = set()
		for st in fromStat:
			cantRob = set()
			for i in range(N):
				move_target = {'1', '2', '3', '4'}
				if st[i] in cantRob:
					continue
				cantRob.add(st[i])
				move_target = move_target.difference(cantRob)
				if not move_target:
					break
				for t in move_target:
					new_stat = st[:i] + t + st[i + 1:]
					if new_stat not in visited:
						toStat.add(new_stat)
						visited.add(new_stat)
		fromStat = toStat
		ans += 1
N = int(input())
a = list(map(int, input().rstrip().split()))
print(Hanoi(a))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys
from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys
from collections import deque

def imprime_plateau(plateau):
	for (num_stick, liste_disques) in enumerate(plateau):
		print('stick {}:'.format(num_stick), end='')
		print(*liste_disques)
	print()

def imprime_tuple_plateau(tuple_plateau):
	for (num_stick, tuple_disque) in enumerate(tuple_plateau):
		print('stick {}:'.format(num_stick), end='')
		print(tuple_disque)

def mvt_possible(tuple_plateau):
	for (num_stick, liste_disques) in enumerate(tuple_plateau):
		if len(liste_disques) > 0:
			for (num_stick_suivant, liste_disques_suivant) in enumerate(tuple_plateau):
				if num_stick_suivant != num_stick:
					if len(liste_disques_suivant) == 0:
						temp = listisation(tuple_plateau)
						temp[num_stick_suivant].append(temp[num_stick].pop())
						yield tuplisation(temp)
					elif liste_disques[-1] < liste_disques_suivant[-1]:
						temp = listisation(tuple_plateau)
						temp[num_stick_suivant].append(temp[num_stick].pop())
						yield tuplisation(temp)

def tuplisation(plateau):
	temp = plateau[:]
	temp[1:4] = sorted(temp[1:4], key=lambda t: t[-1] if t else 0, reverse=True)
	return tuple((tuple(t) for t in temp))

def listisation(tuple_plateau):
	return list((list(stick) for stick in tuple_plateau))

def fini(plateau):
	return all([len(plateau[p]) == 0 for p in range(1, len(plateau))])

def parcours_en_largeur(plateau):
	visites = set()
	depart = tuplisation(plateau)
	q = deque([(depart, 0)])
	visites.add(depart)
	while q:
		(etat, profondeur) = q.popleft()
		if fini(etat):
			return profondeur
		for prochain in mvt_possible(etat):
			if prochain not in visites:
				q.append((prochain, profondeur + 1))
				visites.add(prochain)
N = int(input())
plateau = [[] for _ in range(4)]
distribution = list(map(int, input().rstrip().split()))
for (i, num) in enumerate(reversed(distribution)):
	plateau[num - 1].append(N - i)
print(parcours_en_largeur(plateau))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all((len(x[i]) == 0 for i in range(1, len(x))))

def bfs(x):

	def tuplify(x):
		return tuple((tuple(ele) for ele in x))

	def do_move(state, m):
		y = [list(t) for t in state]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	q = deque()
	start = (tuplify(x), 0)
	q.append(start)
	while q:
		(state, depth) = q.popleft()
		if is_goal(state):
			return depth
		for move in legal_moves(state):
			child_state = do_move(state, move)
			if child_state not in visited:
				visited.add(child_state)
				q.append((child_state, depth + 1))
n = int(input())
R = list(map(int, input().split()))
A = [[] for _ in range(4)]
for i in range(n):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


import math
import os
import random
import re
import sys

def hanoi(a):
	history = set()
	success = tuple(len(a) * [1])

	def move(arrangements, count=1):
		new_arrangements = []
		for a in arrangements:
			for origin in range(1, 5):
				try:
					disc = a.index(origin)
				except ValueError:
					continue
				for peg in range(1, 5):
					if peg == origin:
						continue
					try:
						if a.index(peg) < disc:
							continue
					except ValueError:
						pass
					a_ = a[:]
					a_[disc] = peg
					af = tuple(a_)
					if af in history:
						continue
					if af == success:
						return count
					history.add(af)
					new_arrangements.append(a_)
		return move(new_arrangements, count + 1)
	af = tuple(a)
	if af == success:
		return 0
	history.add(af)
	return move([a])
N = int(input())
a = list(map(int, input().rstrip().split()))
print(hanoi(a))


import math
import os
import random
import re
import sys

def alt_index(x):
	if len(x) > 0:
		return -x[0]
	else:
		return -11

def Hanoi(N, a):
	target = [tuple() for _ in range(4)]
	for i in range(len(a)):
		pos = a[i] - 1
		target[pos] = target[pos] + (i + 1,)
	target = tuple([target[0]] + sorted(target[1:], key=alt_index))
	prev_layer = [(tuple(range(1, N + 1)), tuple(), tuple(), tuple())]
	visited_nodes = {(tuple(range(1, N + 1)), tuple(), tuple(), tuple())}
	depth = 0
	while target not in visited_nodes:
		depth += 1
		curr_layer = []
		for prev_node in prev_layer:
			for k in range(1, 4):
				if len(prev_node[0]) > 0:
					top_disc_1 = prev_node[0][0]
				else:
					top_disc_1 = N + 1
				if len(prev_node[k]) > 0:
					top_disc_2 = prev_node[k][0]
				else:
					top_disc_2 = N + 1
				if not (top_disc_1 == N + 1 and top_disc_2 == N + 1):
					curr_node = [0] * 4
					for p in range(4):
						if p != 0 and p != k:
							curr_node[p] = prev_node[p]
					if top_disc_1 < top_disc_2:
						curr_node[0] = prev_node[0][1:]
						curr_node[k] = (top_disc_1,) + prev_node[k]
					else:
						curr_node[0] = (top_disc_2,) + prev_node[0]
						curr_node[k] = prev_node[k][1:]
					curr_node = tuple([curr_node[0]] + sorted(curr_node[1:], key=alt_index))
					if curr_node not in visited_nodes:
						visited_nodes.add(curr_node)
						curr_layer.append(curr_node)
			for i in range(1, 4):
				if len(prev_node[i]) > 0:
					top_disc_1 = prev_node[i][0]
					for j in range(1, i):
						curr_node = [0] * 4
						for k in range(4):
							if k != i and k != j:
								curr_node[k] = prev_node[k]
						curr_node[i] = prev_node[i][1:]
						curr_node[j] = (top_disc_1,) + prev_node[j]
						curr_node = tuple([curr_node[0]] + sorted(curr_node[1:], key=alt_index))
						if curr_node not in visited_nodes:
							visited_nodes.add(curr_node)
							curr_layer.append(curr_node)
		prev_layer = curr_layer
	print(depth)
N = int(input())
a = list(map(int, input().rstrip().split()))
Hanoi(N, a)


import math
import os
import random
import re
import sys

def towers(N, a):
	rods = [[] for _ in range(4)]
	for disk in range(len(a)):
		rods[a[disk] - 1].append(disk + 1)
	rods = [tuple(sorted(rods[i])) for i in range(4)]
	rods = [rods[0]] + sorted(rods[1:])
	rods = tuple(rods)
	visited = set()
	currRods = [rods]
	nextRods = []
	numMoves = 0
	while True:
		for r in currRods:
			if r in visited:
				continue
			if r == tuple([tuple(range(1, N + 1)), (), (), ()]):
				return numMoves
			visited.add(r)
			for fromRod in range(4):
				for toRod in range(4):
					if len(r[fromRod]) > 0 and (len(r[toRod]) == 0 or r[fromRod][0] < r[toRod][0]):
						disk = r[fromRod][0]
						descendant = [list(tup) for tup in r]
						descendant[fromRod] = descendant[fromRod][1:]
						descendant[toRod] = [disk] + descendant[toRod]
						descendant = [tuple(rod) for rod in descendant]
						descendant = [descendant[0]] + sorted(descendant[1:])
						descendant = tuple(descendant)
						nextRods.append(descendant)
		currRods = list(nextRods)
		nextRods = []
		numMoves += 1
N = int(input())
a = list(map(int, input().rstrip().split()))
print(towers(N, a))


from collections import deque

def legal_moves(x):
	for i in range(len(x)):
		if x[i]:
			for j in range(len(x)):
				if not x[j] or x[i][-1] < x[j][-1]:
					yield (i, j)

def is_goal(x):
	return all([len(x[i]) == 0 for i in range(1, len(x))])

def bfs(x):

	def tuplify(z):
		return tuple((tuple(t) for t in z))

	def do_move(g, m):
		y = [list(t) for t in g]
		y[m[1]].append(y[m[0]].pop())
		y[1:4] = sorted(y[1:4], key=lambda t: t[-1] if t else 0)
		return tuplify(y)
	visited = set()
	start = (tuplify(x), 0)
	q = deque([start])
	visited.add(start)
	while q:
		(node, depth) = q.popleft()
		if is_goal(node):
			return depth
		for move in legal_moves(node):
			child = do_move(node, move)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
N = int(input())
A = [[] for i in range(4)]
R = [int(t) for t in input().split()]
for i in range(N):
	A[R[i] - 1] = [i + 1] + A[R[i] - 1]
print(bfs(A))


from collections import deque

def tuplify(x):
	return tuple((tuple(i) for i in x))

def moves(rods):
	for x in range(4):
		if rods[x]:
			for y in range(4):
				if not rods[y] or rods[y][-1] > rods[x][-1]:
					yield (x, y)

def do_move(rods, x, y):
	rods = [list(r) for r in rods]
	rods[y].append(rods[x].pop())
	rods[1:4] = sorted(rods[1:4], key=lambda t: t[-1] if t else 0)
	return tuplify(rods)

def bfs(rods, n):
	start = (tuplify(rods), 0)
	visited = set()
	visited.add(start)
	q = deque([start])
	while q:
		(cur, depth) = q.popleft()
		if all((len(r) == 0 for r in cur[1:])):
			return depth
		for (x, y) in moves(cur):
			child = do_move(cur, x, y)
			if child not in visited:
				visited.add(child)
				q.append((child, depth + 1))
	return -1
n = int(input())
rods = [[] for _ in range(4)]
for (i, disk) in enumerate(map(int, input().split())):
	rods[disk - 1] = [i] + rods[disk - 1]
print(bfs(rods, n))