Minimum Adjacent Swaps for Legal Shoe Arrangement

Adnan owns the largest shoe store in Baku. One day, a box containing n pairs of shoes arrives. Each pair consists of two shoes of the same size: one for the left foot and one for the right foot. The 2n shoes are placed in a row at positions $0,1,\dots,2n-1$.

An arrangement is called legal if and only if for every integer $i$ with $0\le i<n$, the following conditions hold for the shoes at positions $2i$ and $2i+1$:

• The two shoes have the same size,
• The shoe at position $2i$ is a left shoe,
• The shoe at position $2i+1$ is a right shoe.

Adnan can perform a series of moves. In each move, he chooses two adjacent shoes (i.e. shoes whose positions differ by $1$) and swaps them. Determine the minimum number of swaps needed to reach a legal arrangement.

Note: Due to Luogu's data point limitation, this problem is evaluated using only 100 test cases. To test the complete set of data, there are two separate tasks:

1. Subtask 1-3
2. Subtask 4-6

Both problems are scored out of 50 points and together cover all the test cases.

inputFormat

The input consists of three lines:

1. The first line contains an integer $n$ ($1\le n\le \text{limit}$), the number of pairs of shoes.
2. The second line contains $2n$ integers. The $i$-th integer represents the size of the shoe at position $i-1$.
3. The third line contains a string of length $2n$. Each character is either L or R, where the $i$-th character indicates whether the shoe at position $i-1$ is for the left or right foot respectively.

It is guaranteed that for each size, there is exactly one left shoe and one right shoe.

outputFormat

Output a single integer: the minimum number of adjacent swaps needed to obtain a legal arrangement.

sample

1
5
RL

1