Minimum Adjacent Swaps to Sort Book Titles

You are given a list of book titles. Your task is to determine the minimum number of adjacent swaps required to sort the list of book titles in alphabetical order. In other words, each swap can only exchange two neighboring elements. Formally, if the initial sequence is denoted by \(A\), you need to transform it into a sorted sequence \(A'\) using only adjacent swaps, and your goal is to minimize the number of swaps performed.

Hint: The minimum number of adjacent swaps needed is equal to the number of inversions in the array. Use appropriate sorting or simulation methods to compute this count efficiently for the given constraints.

inputFormat

The first line contains a single integer \(n\) \((1 \le n \le 10^5)\), the number of book titles. The following \(n\) lines each contain one book title, which is a non-empty string without spaces. All titles consist of lowercase English letters.

outputFormat

Output a single integer representing the minimum number of adjacent swaps required to sort the book titles in alphabetical order.

3
zebra
monkey
apple

3