One little Boy likes to play chess. However, one day he got bored with ordinary chess and decided to make a new game to play on a chess board.

After a long time, the Boy has finally made a game and he wants you to play with him.

The rules are as follows: The chess board, where the game is played, is infinitely large. In the game you use only one man - a pawn. The game lasts N+1 seconds. At the begging the pawn is standing at the position (0, 0) for one second, and after that Boy says where the pawn has to go every second, and that is:
'up' - If the pawn has to move up one position
'down' - If the pawn has to move down one position
'left' - If the pawn has to move left one position
'right' - If the pawn has to move right one position
'stay' - If the pawn stays at the same position for one more second

After that you need to determine which position the pawn spent the greatest amount of time on. It may be possible to have more than one position that answers this question, but Boy only wants you to tell him how long the pawn spent at the position.

Input
The first line of the standard input contains one number N representing the number of commands Boy says. Remember that the game lasts N+1 seconds because the pawn stays at the position (0, 0) before Boy's first command, and after each command the pawn stays at that position for exactly one second.

Output
To the standard output write one number that represents maximum time spent at one position.

Sample Input
5
left
up
left
right
right

Sample Output
2

Explanation

On interval 0..1 the pawn is at the position (0, 0), after that Mr. Little Z is giving the commands:
On interval 1..2 the pawn is at the position (-1, 0)
On interval 2..3 the pawn is at the position (-1, 1)
On interval 3..4 the pawn is at the position (-2, 1)
On interval 4..5 the pawn is at the position (-1, 1)
On interval 5..6 the pawn is at the position (0, 1), and the game is over.

And the pawn spent 2 seconds at the position (-1, 1)

Solution
It is pretty simple i just stored everything into array of points (x,y) and at the end found the point in which pawn was the most of the time.

So here is the code in TPW :