Tretis is a classic computer game where game pieces, each consisting of 4 square blocks, fall from the sky into the game area. The game area, in this problem, has 10 columns.
The implementation of the game is currently broken. Therefore, only 3 types of game pieces are generated, shown below. The player cannot move or rotate the pieces. Also, when the pieces fill up a row, nothing disappears.
The 3 possible type of pieces are shown below: left ( - type), middle ( i type), and right (o type).
You are provided with the sequence of the falling game pieces. For each game piece, you know that type and the left-most column where it is falling. You should find the highest level of the pieces in the game at the end. (You may assume that the game area has infinite height.)
Input
The first line contains an integer N (1