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

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

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

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

Input

첫 줄에 미어캣의 수 $N$이 주어진다. ($3 \leq N \leq 5\,000$)

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

모든 $A_i$는 서로 다르다.

Output

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

Examples

Input 1

5
5 L
2 R
3 R
4 R
1 L

Output 1

4

Input 2

7
7 R
1 L
6 R
3 L
5 L
4 R
2 R

Output 2

4