테트리스

소냐가 장난감 상자에서 오래된 테트리스 게임기를 찾았다. 판은 가로 3칸, 세로 10칸이다. 행은 위에서부터 1번에서 10번, 열은 왼쪽에서부터 1번에서 3번이다.

이 게임에는 0번부터 9번까지 10가지 조각이 있고, 모든 조각은 3 x 3 상자 안에 들어간다. 아래 그림에서 #은 채워진 칸, .은 빈 칸이다.

  0       1       2       3       4

 .#.     ###     ##.     .##     ##.
 ###     #..     .##     .#.     .#.
 .#.     #..     ..#     ##.     .##

  5       6       7       8       9

 .#.     .#.     .#.     .##     ..#
 .#.     ###     .##     ###     ###
 ###     .##     ##.     ##.     ##.

조각은 끝없이 내려온다. 수열 $a_1, a_2, \dots, a_n$이 계속 반복되므로 $k$번째 조각의 모양은 $a_{((k - 1) \bmod n) + 1}$이다.

조각이 떨어지기 전에 소냐는 조각을 90도의 배수만큼 돌리고 좌우로 옮긴다. 뒤집을 수는 없다. 조각은 3개 열 안에 모두 들어가야 한다. 그다음 조각은 회전 상태와 열을 그대로 유지한 채 한 행씩 곧장 아래로 내려가고, 한 행 더 내려가면 판 밖으로 나가거나 채워진 칸과 겹치게 되는 바로 직전에 멈춘다.

조각이 멈추면 세 칸이 모두 채워진 행은 사라지고, 사라진 행보다 위에 있던 행은 자기 아래에서 사라진 행의 수만큼 내려온다.

행이 사라진 뒤 맨 위 3개 행에 채워진 칸이 하나라도 있으면 게임이 끝난다. 조각은 멈추는 순간 떨어진 것으로 세므로, 게임을 끝낸 조각도 개수에 포함한다.

게임이 이어지는 동안 맨 위 3개 행은 비어 있으므로, 어떤 조각이든 항상 놓을 수 있다.

소냐는 떨어지는 조각을 최대한 많이 만들고 싶다. 게임이 영원히 끝나지 않을 수도 있고, 그럴 때는 아예 시작하지 않는 편이 낫다.

첫째 줄에 수열 $a$의 길이 $n$이 주어진다 ($1 \le n \le 50$).

둘째 줄에 수열의 원소 $a_1, a_2, \dots, a_n$이 주어진다 ($0 \le a_i \le 9$).

게임이 끝나기 전까지 떨어질 수 있는 조각 개수의 최댓값을 한 줄에 출력한다. 소냐가 조각을 영원히 떨어뜨릴 수 있으면 $-1$을 출력한다.