시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 7 2 2 33.333%

문제

동혁이는 테트리스와 매우 비슷한 아래와 같은 게임을 즐기는데, 이 게임은 가로 3, 세로 300 길이의 직사각형 모양의 게임 필드에서 이루어진다. 이 게임에는 아래와 같은 일곱 개의 타일이 있다.

동혁이는 각각의 타일을 돌릴 수 있다. 돌린다는 것은 90도, 180도, 270도로 왼쪽 또는 오른쪽으로 타일을 회전시키는 것을 의미하여, 뒤집는 것은 허용되지 않는다. (즉 2번 모양의 타일을 돌려서 3번 모양의 타일로 만들 수는 없다.)

처음에 게임 필드는 비어 있다. 게임이 시작되면 지정된 순서대로 타일들이 게임 필드의 위쪽에서 아래쪽으로 떨어지게 된다. 이를 적절히 좌우로 이동시키거나 회전시켜서 아래부터 순서대로 쌓아 나가야 하는데, 타일끼리 서로 겹쳐서는 안 된다. 또한 타일이 게임 필드 밖으로 나가서도 안 된다.

예를 들어 1번 모양의 타일을 돌리면 가로로 길이가 4가 되기 때문에, 돌릴 수 없다. 또한 2번 모양의 타일은 가로로 길이가 2이므로 첫째, 둘째 가로선에 떨어질 수도 있고, 둘째, 셋째 가로선에 떨어질 수도 있다.

한 번 타일이 필드 아래에 내려와서 쌓인 후 다음 타일이 내려왔으면, 쌓인 타일은 다시 이동하거나 회전할 수 없다. 타일이 내려갈 때도 마찬가지이다, 방향을 정해서 내려가기 시작했으면, 중간에 타일을 이동하거나 회전하는 것은 불가능하다.

타일이 게임 필드에 들어오는 순서가 주어졌을 때, 모든 타일을 게임 필드에 가능한 최소의 높이로 쌓았을 때 그 높이를 출력하는 프로그램을 작성하시오. 높이란 아래로부터 타일이 쌓여져 있는 최소의 칸이다. 즉 다시 이야기하면, 첫째, 둘째, 셋째 가로칸 모두 아래로부터 K번째 세로칸까지만 타일이 놓여 있도록 하는 최소의 K를 찾으면 된다.

입력

첫째 줄에 타일의 개수 N이 주어진다. (1≤N≤100) 이어 N개의 줄에 걸쳐 순서대로 떨어지는 타일이 몇 번 모양인지를 나타내는 자연수가 각 줄에 하나씩 주어진다. 주어지는 자연수는 7 이하이다.

출력

첫째 줄에 최소의 높이 K를 출력한다.

예제 입력

3
4
5
1

예제 출력

5

힌트