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 a_i, and the color of this ball is represented by a letter c_i. c_i = `W` represents the ball is white; c_i = `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:

* Swap two adjacent balls.



Find the minimum number of operations required to achieve the objective.

Constraints

* 1 ≤ N ≤ 2000
* 1 ≤ a_i ≤ N
* c_i = `W` or c_i = `B`.
* If i ≠ j, (a_i,c_i) ≠ (a_j,c_j).

Input

Input is given from Standard Input in the following format:


N
c_1 a_1
c_2 a_2
:
c_{2N} a_{2N}


Output

Print the minimum number of operations required to achieve the objective.

Examples

Input

3
B 1
W 2
B 3
W 1
W 3
B 2


Output

4


Input

4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1


Output

18


Input

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


Output

41
from itertools import accumulate

N = int(input())
balls = []

# 初期位置を覚えておく
placeB = [0] * N
placeW = [0] * N

# 入力処理 & 初期位置処理
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    balls.append([c, a])
    if c == "B":
        placeB[a-1] = i
    else:
        placeW[a-1] = i


costB = [[0]*(2*N+1) for i in range(N+1)]  # i番目まででjより大きいB
costW = [[0]*(2*N+1) for i in range(N+1)]  # i番目まででjより大きいW

for i in range(N):
    for j in range(2*N):
        if balls[j][1] > i:
            if balls[j][0] == "B":
                costB[i][j+1] = 1
            else:
                costW[i][j+1] = 1

# 累積和
costB = [list(accumulate(cB)) for cB in costB]
costW = [list(accumulate(cW)) for cW in costW]

# dp
dp = [[float('inf')]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for b in range(N+1):
    for w in range(N+1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b-1][w] + costB[b][placeB[b-1]] + costW[w][placeB[b-1]])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w-1] + costW[w][placeW[w-1]] + costB[b][placeW[w-1]])

print(dp[N][N])
