ミーアキャット $N$匹からなるミーアキャットの家族が集団生活をしている。昼間はミーアキャットたちが天敵に備えるために巣穴から出て、$1$次元座標上で見張りを行う。各ミーアキャットは見張りをするとき、自分の位置と見る方向（左または右のいずれか）が決まっており、見張りをしている間は自分の見る方向を変えることができない。

ミーアキャットの家族内のすべてのミーアキャットの身長は互いに異なり、自分より背の高いミーアキャットが自分の見ている方向に立っている場合、そのミーアキャットは見張りをすることができない。これを気の毒に思ったあなたは、ミーアキャットの家族に気づかれずに以下の行動を自由に行うことができる。

• 同じ方向を見ているミーアキャットを2匹選び、互いの位置を入れ替える。

上の行動を適切に行ったとき、見張りをすることができるミーアキャットは最大で何匹になるかを求めよ。

入力

最初の行にミーアキャットの数 $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