题目描述

给定 $N$ 个仅由小写英文字母组成的字符串 $S_1,\dots,S_N$。你可以以任意顺序、任意次数（包括 $0$ 次）进行以下两种操作：

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

请你求出，为了使所有操作结束后，对于每个 $1 \leq i \leq N-1$ 都有 $S_i \leq S_{i+1}$（按字典序），所需操作总次数的最小值。

字典序的定义如下：设字符串 $S = S_1S_2\ldots S_{|S|}$，$T = T_1T_2\ldots T_{|T|}$，其中 $|S|, |T|$ 分别表示 $S, T$ 的长度。$S$ 在字典序上小于 $T$ 当且仅当满足以下两条之一：

1. $|S| < |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$ 的字符。

输入格式

输入按以下格式从标准输入读入：

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出一个整数，表示所需操作总次数的最小值。

样例 1

输入

5
ab
rac
a
dab
ra

输出

3

样例 2

输入

3
kitekuma
nok
zkou

输出

0

样例 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

输出

175

说明/提示

限制条件

• 输入的所有数值均为整数。
• $2 \leq N \leq 3 \times 10^5$
• $S_i$ 由小写英文字母组成。
• $1 \leq |S_i|$
• $|S_1| + |S_2| + \dots + |S_N| \leq 3 \times 10^5$

样例解释 1

下面给出一种操作方案：

• 交换 $S_2$ 和 $S_3$。此时 $(S_1,\ldots,S_5) = ($ab, a, rac, dab, ra$)$。
• 给每个字符串末尾添加 z。此时 $(S_1,\ldots,S_5) = ($abz, az, racz, dabz, raz$)$。
• 交换 $S_3$ 和 $S_4$。此时 $(S_1,\ldots,S_5) = ($abz, az, dabz, racz, raz$)$。

此时对于所有 $i = 1,\ldots,N-1$，都有 $S_i \leq S_{i+1}$。无法通过少于 $3$ 次操作达到目标，因此输出 $3$。

样例解释 2

在进行任何操作前，所有 $i = 1,\ldots,N-1$ 都满足 $S_i \leq S_{i+1}$。

样例解释 3

请注意，可能存在 $i \neq j$ 使得 $S_i = S_j$。

由 ChatGPT 4.1 翻译