A family of $N$ meerkats lives in a group. During the day, the meerkats come out of their burrow and stand on a one-dimensional coordinate line to keep watch for predators. When standing guard, each meerkat has a fixed position and a direction (either left or right) they are facing; during the watch, they cannot change the direction they are facing.

All meerkats in the family have distinct heights. A meerkat cannot see over the lookout if a taller meerkat is standing in the direction they are facing. Taking pity on them, you can perform the following action arbitrarily without the meerkats noticing:

• Choose two meerkats facing the same direction and swap their positions.

Determine the maximum number of meerkats that can see over the lookout after performing the above actions appropriately.

Input

The first line contains the number of meerkats $N$. ($3 \leq N \leq 5\,000$)

The next $N$ lines contain information about the meerkats. For all $1 \leq i \leq N$, the $(i+1)$-th line contains an integer $A_i$ representing the height of the meerkat at the $i$-th position from the left, and a character $D_i$ representing the direction it is facing, separated by a space. ($1\leq A_i \leq N$) $D_i$ is given as L for left or R for right.

All values $A_i$ are distinct.

Output

Print the maximum number of meerkats that can see over the lookout.

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