E. Snake Moves
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing the classical snake game on your phone, where a snake moves around on an infinite grid. However in this game, the snake has been programmed with a series of moves represented as a string. The characters 'U', 'D', 'L', and 'R' in the string cause the snake to move up, down, left, and right, respectively. The snake cannot visit the same cell twice in fear of colliding with itself.

In this version of the game, you want to find out the longest substring of the string of moves such that the snake never visits the same cell twice.

Input

The first line of input is n (1 ≤ n ≤ 106), the length of the string of snake moves.

The second line contains the string of snake moves where each character is in the set {'L', 'R', 'U', 'D'}.

Output

Output a single line with the length of the longest substring of moves such that the snake would not visit the same cell twice if it followed those moves.

Examples
Input
4
RULD
Output
3
Input
13
RRDDLLUUURDDR
Output
10
Input
3
RRU
Output
3
Input
2
RL
Output
1