Tetris

Time limit2.5sMemory limit512 MB

Summary

On a 3-wide, 10-tall Tetris board, pieces from a repeating shape sequence arrive forever; maximize how many land before the top fills, or output -1 if play can continue indefinitely.

Level: Hard8 of 10
Topics: Dynamic programming, Simulation, Implementation, Greedy
Solved: No attempts yet

Problem

Sonya found an old Tetris game in her toy box. The board is 3 cells wide and 10 cells tall. Rows are numbered 1 to 10 from the top, columns 1 to 3 from the left.

The game has 10 piece shapes, numbered 0 to 9, and every shape fits in a 3 by 3 box. In the picture below a # is a filled cell and a . is an empty cell.

  0       1       2       3       4

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

  5       6       7       8       9

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

Pieces arrive in an endless stream. The sequence $a_1, a_2, \dots, a_n$ repeats forever, so the $k$ -th piece has shape $a_{((k - 1) \bmod n) + 1}$ .

Before a piece starts falling, Sonya rotates it by any multiple of 90 degrees and shifts it left or right. She cannot flip it over. The piece has to fit inside the 3 columns. The piece then falls straight down one row at a time, keeping its rotation and its columns, and it stops right before the step that would take it off the board or onto a filled cell.

Once the piece stops, every row whose 3 cells are all filled is deleted, and every row above a deleted row moves down by the number of deleted rows below it.

The game is over as soon as a filled cell sits in the top 3 rows after the deletions. A piece counts as fallen the moment it stops, so the piece whose landing ends the game is counted as well.

While the game is running the top 3 rows are empty, so every piece can always be placed.

Sonya wants as many pieces as possible to fall. The game can also go on forever, and in that case she should not start playing.

Input

The first line contains one integer $n$ ( $1 \le n \le 50$ ), the length of the sequence $a$ .

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 9$ ), the elements of the sequence.

Output

Print one integer, the largest number of pieces that can fall before the game is over. Print $-1$ if Sonya can keep the pieces falling forever.

Examples3

Example 1
Input
```
1
0
```
Expected output
```
4
```
Example 2
Input
```
2
3 4
```
Expected output
```
12
```
Example 3
Input
```
3
5 1 1
```
Expected output
```
-1
```