Une famille de suricates composée de $N$ suricates vit en groupe. Pendant la journée, les suricates sortent de leur terrier pour monter la garde sur une coordonnée unidimensionnelle, afin de se défendre contre les prédateurs. Lorsqu'ils montent la garde, chaque suricate a une position déterminée et une direction de regard, soit vers la gauche, soit vers la droite ; il ne peut pas changer de direction pendant qu'il monte la garde.

Tous les suricates de la famille ont des tailles différentes, et un suricate ne peut pas voir au-delà d'un suricate plus grand que lui qui se tient dans la direction qu'il regarde. Ayant pitié d'eux, vous pouvez effectuer librement l'action suivante sans que la famille de suricates ne s'en aperçoive :

• Choisissez deux suricates qui regardent dans la même direction et échangez leurs positions.

En effectuant cette action de manière appropriée, déterminez le nombre maximum de suricates qui peuvent voir au-delà.

Entrée

La première ligne contient le nombre $N$ de suricates. ($3 \leq N \leq 5\,000$)

Les $N$ lignes suivantes contiennent les informations sur les suricates. Pour tout $1 \leq i \leq N$, la $(i+1)$-ième ligne contient un entier $A_i$ représentant la taille du $i$-ième suricate depuis la gauche, et un caractère $D_i$ représentant la direction dans laquelle il regarde, séparés par une espace. ($1\leq A_i \leq N$) $D_i$ vaut L s'il regarde à gauche, et R s'il regarde à droite.

Tous les $A_i$ sont distincts.

Sortie

Affichez sur la première ligne le nombre maximum de suricates qui peuvent voir au-delà.

Exemples

Entrée 1

5
5 L
2 R
3 R
4 R
1 L

Sortie 1

4

Entrée 2

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

Sortie 2

4