테트리스 쌓기

동혁이는 테트리스와 매우 비슷한 게임을 한다. 게임 필드는 가로 3칸, 세로 300칸인 직사각형이고, 사용할 수 있는 타일은 아래의 일곱 종류이다.

각 타일은 왼쪽 또는 오른쪽으로 90도씩 회전할 수 있다. 180도와 270도 회전도 가능하지만, 뒤집기는 할 수 없다. 따라서 2번 타일을 회전해서 3번 타일로 만들 수는 없다.

처음 필드는 비어 있다. 게임이 시작되면 주어진 순서대로 타일이 위에서 아래로 떨어진다. 각 타일은 떨어지기 전에 회전 방향과 가로 위치를 정할 수 있으며, 정한 뒤에는 떨어지는 도중에 이동하거나 회전할 수 없다. 타일은 서로 겹칠 수 없고, 필드 밖으로 나갈 수 없다.

1번 타일은 회전하면 가로 길이가 4칸이 되므로 가로 3칸인 필드에는 회전한 상태로 놓을 수 없다. 2번 타일은 가로 길이가 2칸인 방향에서는 1-2번째 열 또는 2-3번째 열에 놓을 수 있다.

한 타일이 아래로 내려와 쌓인 뒤 다음 타일이 내려오면, 이미 쌓인 타일은 다시 움직이거나 회전할 수 없다.

모든 타일을 주어진 순서대로 쌓되, 최종 높이가 최소가 되도록 하라. 높이 K는 아래에서부터 K번째 행까지만 세 열의 모든 타일이 들어가도록 하는 최소의 K이다.

첫째 줄에 타일의 개수 N이 주어진다. (1 ≤ N ≤ 100)

이어서 N개의 줄에 걸쳐, 순서대로 떨어지는 타일의 번호가 한 줄에 하나씩 주어진다. 각 번호는 1 이상 7 이하의 자연수이다.

최종 높이를 최소로 만들었을 때의 높이 K를 첫째 줄에 출력한다.