Семья сурикатов, состоящая из $N$ сурикатов, ведёт коллективный образ жизни. Днём сурикаты выходят из норы, чтобы нести стражу на одномерной координатной прямой, защищаясь от хищников. Когда каждый сурикат стоит на страже, его положение и направление взгляда (влево или вправо) фиксированы, и он не может изменить направление взгляда во время дежурства.

Рост всех сурикатов в семье различен. Если сурикат большего роста стоит в направлении взгляда данного суриката, то этот сурикат не может наблюдать. Сжалившись над ними, вы можете незаметно для семьи сурикатов сколько угодно раз выполнять следующее действие:

• Выбрать двух сурикатов, смотрящих в одном направлении, и поменять их местами.

Определите, какое максимальное количество сурикатов сможет наблюдать после выполнения описанных действий.

Входные данные

В первой строке дано число сурикатов $N$ ($3 \leq N \leq 5\,000$).

В следующих $N$ строках дана информация о сурикатах. Для всех $1 \leq i \leq N$ в $(i+1)$-й строке через пробел даны целое число $A_i$ — рост суриката, стоящего на $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