Minimum Adjacent Swaps to Sort String

You are given a string s of length n. Your task is to find the minimum number of adjacent swaps required to rearrange the characters of s so that they are in lexicographical order. In other words, you need to transform s into sorted(s) via a series of adjacent swaps. It can be shown that the minimum number of swaps needed is equal to the number of inversions in the sequence. For two indices \(i\) and \(j\) with \(i s[j]\) in lexicographical order.

Note: The input is read from standard input and the output is printed to standard output.

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the length of the string.
• The second line contains the string s, which consists of \(n\) lowercase English letters.

outputFormat

Output a single integer representing the minimum number of adjacent swaps needed to sort the string in lexicographical order.

5
bacde

1