C. 미어캣
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

미어캣 N마리로 구성된 미어캣 가족이 집단생활을 하고 있다. 낮에는 미어캣들이 천적에 대응하기 위해 굴에서 나와 1차원 좌표에서 보초를 선다. 각 미어캣은 보초를 설 때 자신의 위치와 바라보는 방향이 왼쪽 혹은 오른쪽 중 하나로 정해져 있으며, 보초를 서는 동안에는 자신이 바라보는 방향을 바꿀 수 없다.

미어캣 가족 내의 모든 미어캣의 키는 서로 다르며 자신보다 키가 큰 미어캣이 자신이 바라보는 방향에 서 있는 경우 망을 볼 수 없다. 이를 불쌍하게 여긴 당신은 미어캣 가족이 눈치채지 못하게 아래의 행동을 자유롭게 수행할 수 있다.

  • 같은 방향을 바라보는 미어캣 둘을 고르고, 서로 자리를 바꾼다.

위의 행동을 적절히 수행했을 때 망을 볼 수 있는 미어캣은 최대 몇 마리인지 구해보자.

Input

첫 줄에 미어캣의 수 N이 주어진다. (3 ≤ N ≤ 5 000)

둘째 줄부터 N개의 줄에 걸쳐 미어캣에 대한 정보가 주어진다. 모든 1 ≤ i ≤ N에 대해, (i + 1)번째 줄에 왼쪽에서 i번째에 위치한 미어캣의 키를 나타내는 정수 Ai, 바라보고 있는 방향을 나타내는 문자 Di가 공백을 사이에 두고 주어진다. (1 ≤ Ai ≤ N) Di는 왼쪽이면 L, 오른쪽이면 R로 주어진다.

모든 Ai는 서로 다르다.

Output

첫 줄에 망을 볼 수 있는 미어캣은 최대 몇 마리인지 출력한다.

Examples
Input
5
5 L
2 R
3 R
4 R
1 L
Output
4
Input
7
7 R
1 L
6 R
3 L
5 L
4 R
2 R
Output
4