Score: $1000$ points

问题陈述

给定 $N$ 个字符串 $S_1, \dots, S_N$，由小写英文字母组成。考虑执行以下两种类型的操作，每种操作可以执行零次或多次，且执行顺序任意：

• 选择一个小写字母 $c$。将 $c$ 附加到所有 $1 \leq i \leq N$ 的 $S_i$ 的末尾。
• 选择一个整数 $i$，使得 $1 \leq i \leq N-1$。交换 $S_i$ 和 $S_{i+1}$。

找到使 $S_i \leq S_{i+1}$ 在字典序上对所有 $1 \leq i \leq N-1$ 成立的最小总操作数。

什么是字典序？

如果满足以下 1. 或 2. 中的任一条件，我们说字符串 $S = S_1S_2\ldots S_{|S|}$ 字典序上小于字符串 $T = T_1T_2\ldots T_{|T|}$。这里，$|S|$ 和 $|T|$ 分别表示 $S$ 和 $T$ 的长度。

1. $|S| \lt |T|$ 且 $S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}$。
2. 存在一个整数 $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ 使得以下两个条件同时成立：
   • $S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}$。
   • 字母 $S_i$ 在字母表顺序上先于 $T_i$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given $N$ strings $S_1, \dots, S_N$ consisting of lowercase English letters. Consider performing the following two types of operations zero or more times in any order:

• Choose one lowercase letter $c$. Append $c$ to the end of $S_i$ for all $1 \leq i \leq N$.
• Choose an integer $i$ such that $1 \leq i \leq N-1$. Swap $S_i$ and $S_{i+1}$.

Find the minimum total number of operations required to make $S_i \leq S_{i+1}$ in lexicographical order for all $1 \leq i \leq N-1$.

What is lexicographical order?

A string $S = S_1S_2\ldots S_{|S|}$ is said to be lexicographically smaller than a string $T = T_1T_2\ldots T_{|T|}$ if 1. or 2. below holds. Here, $|S|$ and $|T|$ denote the lengths of $S$ and $T$, respectively.

1. $|S| \lt |T|$ and $S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}$.
2. There is an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ such that both of the following hold:
   • $S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}$.
   • The letter $S_i$ comes before $T_i$ in alphabetical order.

Constraints

• All input values are integers.
• $2 \le N \le 3 \times 10^5$
• $S_i$ is a string consisting of lowercase English letters.
• $1 \le |S_i|$
• $|S_1| + |S_2| + \dots + |S_N| \le 3 \times 10^5$

Input

The input is given from Standard Input in the following format:

$N$

$S_1$

$S_2$

$\vdots$

$S_N$

Output

Print the answer in a single line.

Sample Input 1

5
ab
rac
a
dab
ra

Sample Output 1

3

Here is one way to operate.

• Swap $S_2$ and $S_3$. Now $(S_1, \ldots, S_5) = ($ab, a, rac, dab, ra$)$.
• Append z to the end of each string. Now $(S_1, \ldots, S_5) = ($abz, az, racz, dabz, raz$)$.
• Swap $S_3$ and $S_4$. Now $(S_1, \ldots, S_5) = ($abz, az, dabz, racz, raz$)$. At this point, we have $S_i \leq S_{i+1}$ for all $i = 1, \ldots, N-1$.

It is impossible to make $S_i \leq S_{i+1}$ for all $i = 1, \ldots, N-1$ with fewer than three operations, so you should print $3$.

Sample Input 2

3
kitekuma
nok
zkou

Sample Output 2

0

Before any operation is performed, we have $S_i \leq S_{i+1}$ for all $i = 1, \ldots, N-1$.

Sample Input 3

31
arc
arrc
rc
rac
a
rc
aara
ra
caac
cr
carr
rrra
ac
r
ccr
a
c
aa
acc
rar
r
c
r
a
r
rc
a
r
rc
cr
c

Sample Output 3

175

Note that we may have $S_i = S_j$ for $i \neq j$.