Sorted and Sorted
Problem Statement
There are 2N balls, N white and N black, arranged in a row. The integers from 1 through N are written on the white balls, one on each ball, and they are also written on the black balls, one on each ball.
The integer written on the i-th ball from the left (1 ≤ i ≤ 2N) is ai, and the color of this ball is represented by a letter ci.
ci = W represents the ball is white; ci = B represents the ball is black.
Takahashi the human wants to achieve the following objective:
- For every pair of integers (i,j) such that 1 ≤ i < j ≤ N, the white ball with i written on it is to the left of the white ball with j written on it.
- For every pair of integers (i,j) such that 1 ≤ i < j ≤ N, the black ball with i written on it is to the left of the black ball with j written on it.
In order to achieve this, he can perform the following operation:
Find the minimum number of operations required to achieve the objective.
Constraints
- 1 ≤ N ≤ 2000
- 1 ≤ ai ≤ N
- ci =
W or ci = B.
- If i ≠ j, (ai,ci) ≠ (aj,cj).
Input
Input is given from Standard Input in the following format:
N
c1 a1
c2 a2
:
c2N a2N
Output
Print the minimum number of operations required to achieve the objective.
Sample Input 1
3
B 1
W 2
B 3
W 1
W 3
B 2
Sample Output 1
4
The objective can be achieved in four operations, for example, as follows:
- Swap the black 3 and white 1.
- Swap the white 1 and white 2.
- Swap the black 3 and white 3.
- Swap the black 3 and black 2.
Sample Input 2
4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1
Sample Output 2
18
Sample Input 3
9
W 3
B 1
B 4
W 1
B 5
W 9
W 2
B 6
W 5
B 3
W 8
B 9
W 7
B 2
B 8
W 4
W 6
B 7
Sample Output 3
41