Gia đình meerkat gồm $N$ con meerkat đang sống tập thể. Ban ngày, các chú meerkat ra khỏi hang để canh gác trên tọa độ một chiều nhằm đối phó với kẻ thù. Mỗi meerkat khi canh gác có vị trí và hướng nhìn (trái hoặc phải) được xác định trước, và trong suốt thời gian canh gác không thể đổi hướng.

Tất cả các meerkat trong gia đình đều có chiều cao khác nhau; nếu một meerkat cao hơn đứng ở hướng nó nhìn, thì nó không thể quan sát được. Thương xót chúng, bạn có thể thực hiện hành động dưới đây một cách tự do mà không bị gia đình meerkat phát hiện.

• Chọn hai meerkat nhìn cùng hướng và đổi chỗ cho nhau.

Nếu thực hiện hành động trên một cách hợp lý, hãy tìm số lượng meerkat tối đa có thể quan sát được.

Dữ liệu vào

Dòng đầu tiên chứa số lượng meerkat $N$. ($3 \leq N \leq 5\,000$)

Sau đó, $N$ dòng tiếp theo, mỗi dòng chứa thông tin về một meerkat. Với mọi $1 \leq i \leq N$, dòng thứ $(i+1)$ chứa số nguyên $A_i$ là chiều cao của meerkat ở vị trí thứ $i$ từ trái sang, và ký tự $D_i$ là hướng nhìn, cách nhau bởi một dấu cách. ($1 \leq A_i \leq N$) $D_i$ là L nếu nhìn trái, R nếu nhìn phải.

Tất cả các $A_i$ đôi một khác nhau.

Dữ liệu ra

In ra một dòng chứa số lượng meerkat tối đa có thể quan sát được.

Ví dụ

Dữ liệu vào 1

5
5 L
2 R
3 R
4 R
1 L

Dữ liệu ra 1

4

Dữ liệu vào 2

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

Dữ liệu ra 2

4