Minimum Adjacent Swaps for Equal Halves

Given a positive integer n and a string S of length 2n consisting of lowercase letters, you are allowed to swap any two adjacent characters (each swap counts as one operation). The objective is to transform S into a string of the form $$X X$$ (i.e. the first n letters are identical to the last n letters) using the minimum number of operations.

Note: It is guaranteed that every letter in S occurs an even number of times so that the transformation is always possible.

Explanation:

• You may arbitrarily choose the target string $$T = X X$$ as long as the multiset of letters in X is exactly half of those in S. In particular, one optimal strategy is to construct X in the order in which the first half of the needed occurrences appear in S.
• Then, the task reduces to computing the minimum number of adjacent swaps required to transform S into this target configuration.

Hint: One effective method is to determine, for each letter, the first $$\frac{\text{count}(\text{letter})}{2}$$ occurrences (as they appear in S) that will form the left half. Let this left half be X and define T = X X. Then match each occurrence in T with its corresponding occurrence in S (in order) and compute the inversion count of the resulting permutation. This inversion count equals the minimum number of adjacent swaps needed.

inputFormat

The first line contains a positive integer n (1 ≤ n). The second line contains a string S of length 2n composed of lowercase letters. It is guaranteed that each letter in S appears an even number of times.

outputFormat

Output a single integer representing the minimum number of adjacent swaps required to transform S into a string of the form $$X X$$, where the two halves are identical.

sample

2
abba

1