猫鼬 $N$ 只组成的猫鼬家族过着群体生活。白天，猫鼬们为了应对天敌，从洞穴中出来，在一维坐标上站岗。每只猫鼬站岗时，它的位置和朝向（左或右）是确定的，并且站岗期间不能改变朝向。

猫鼬家族中所有猫鼬的身高各不相同，如果比自己高的猫鼬站在自己朝向的方向上，则无法放哨。同情它们的你可以在不被猫鼬家族察觉的情况下自由执行以下操作：

• 选择两只朝向相同的猫鼬，交换它们的位置。

通过适当执行上述操作，求最多有多少只猫鼬能够放哨。

输入

第一行给出猫鼬的数量 $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$ 互不相同。

输出

第一行输出最多有多少只猫鼬能够放哨。

样例

输入格式 1

5
5 L
2 R
3 R
4 R
1 L

输出格式 1

4

输入格式 2

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

输出格式 2

4