Sorted and Sorted
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.
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.
- 1 ≤ N ≤ 2000
- 1 ≤ ai ≤ N
- ci =
W or ci =
- If i ≠ j, (ai,ci) ≠ (aj,cj).
Input is given from Standard Input in the following format:
Print the minimum number of operations required to achieve the objective.
Sample Input 1
Sample Output 1
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
Sample Output 2
Sample Input 3
Sample Output 3