32027번 - 미어캣

문제

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

보초를 서고 있는 귀여운 미어캣 다섯 마리

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

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

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

입력

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

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

모든 A_i는 서로 다르다.

출력

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

제한

힌트