Cho \(N \times 2\) quả bóng gồm \(N\) quả bóng màu vàng và \(N\) quả bóng màu xanh dương được đặt trong một hàng dọc được kí hiệu là \(color_i\) và \(a_i\). Trong đó \(color_i\) tượng trưng cho màu của quả bóng, \(color_i\) là yellow nếu quả bóng đó là màu vàng và \(color_i\) là blue nếu quả bóng đó là màu xanh dương và \(a_i\) là số thứ tự của quả bóng \((1\le a_i\le N)\).

Lúc đầu các quả bóng được sắp xếp ngẫu nhiên, shiba muốn sắp xếp các quả bóng bằng cách hoán đổi vị trí của hai quả bóng liền kề nhau cho đến khi \(N\) quả bóng màu vàng được sắp theo tăng dần từ trên xuống dưới theo số thứ tự và \(N\) quả bóng màu xanh dương được sắp theo tăng dần từ trên xuống dưới theo số thứ tự

Biết rằng shiba có thể thay đổi vị trí nhiều lần hoặc có thể không cần đổi, và mỗi lần chỉ được hoán đổi vị trí của hai quả bóng liền kề nhau. shiba chỉ quan tâm \(N\) quả bóng màu vàng được sắp theo tăng dần hay chưa (tương tự với quả bóng màu xanh dương) mà không cần quan tâm màu gì đứng trước màu gì.

Yêu cầu: Bạn hãy tìm số lần thực hiện thao tác ít nhất có thể để các quả bóng được sắp xếp theo đúng mong muốn của shiba.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 2000)\).
• \(N \times 2\) Dòng tiếp theo mỗi dòng chứa hai giá trị \(color_i\) và \(a_i\)
  \((color_i =\) yellow hoặc \(color_i =\) blue, \(1 \le a_i \le N)\).
• Input luôn đảm bảo rằng số thứ tự của mỗi màu không bị trùng lặp.

Output

• In ra số lần thực hiện thao tác ít nhất có thể để các quả bóng được sắp xếp theo đúng các điều kiện trên.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 10\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
yellow 2
blue 3
yellow 1
blue 1
blue 2
yellow 3

4

5
blue 3
blue 2
blue 5
yellow 4
blue 4
yellow 1
yellow 5
blue 1
yellow 2
yellow 3

15