Description

Given two strings $a$, $b$ of equal length, each consisting only of uppercase letters, you may swap two adjacent characters in $a$ at a time. Find the minimum number of swaps needed so that the string obtained from $a$ becomes identical to $b$.

Input Format

The first line contains an integer $n$, the length of the strings.

The second line contains a string of length $n$, denoting $a$.

The third line contains a string of length $n$, denoting $b$.

Output Format

Output a single integer on one line, the minimum number of swaps.

3
ABC
BCA

2

Hint

Constraints

• For 30% of the testdata, it is guaranteed that $n \leq 10^3$.
• For 100% of the testdata, $1 \leq n \leq 10^6$, $a$, $b$ contain only uppercase letters, and the testdata guarantees that $a$ can be transformed into $b$.

Translated by ChatGPT 5