分数: 1000 点
问题陈述
你被给予 N 字符串 S_1, \dots, S_N 由小写英文字母组成。考虑以任意顺序执行以下两种类型的操作零次或多次:
- 选择一个小写字母 c。追加 c 到年底 S_i 对于所有人 1 \leq i \leq N.
- 选择一个整数 i 这样 1 \leq i \leq N-1。互换 S_i 和 S_{i+1}.
找出完成任务所需的最少操作总数 S_i \leq S_{i+1} 按字典顺序排列 1 \leq i \leq N-1.
什么是字典顺序?
一个字符串 S = S_1S_2\ldots S_{|S|} 据说是 按字典顺序较小 比字符串 T = T_1T_2\ldots T_{|T|} 如果下面的 1. 或 2. 成立。 在这里, |S| 和 |T| 表示的长度 S 和 T。
- |S| \lt |T| 和 S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
- 有一个整数 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 按字母顺序排列。
约束
- 所有输入值均为整数。
- 2 \le N \le 3 \times 10^5
- S_i 是由小写英文字母组成的字符串。
- 1 \le |S_i|
- |S_1| + |S_2| + \dots + |S_N| \le 3 \times 10^5
输入
输入由标准输入按以下格式给出:
N S_1 S_2 \vdots S_N
输出
在一行中打印答案。
示例输入 1
5 ab rac a dab ra
示例输出 1
3
这是一种操作方法。
- 交换 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)。此时,我们有 S_i \leq S_{i+1} 对于所有人 i = 1, \ldots, N-1.
不可能使 S_i \leq S_{i+1} 对于所有人 i = 1, \ldots, N-1 操作少于三个,因此您应该打印 3.
示例输入 2
3 kitekuma nok zkou
示例输出 2
0
在执行任何操作之前,我们有 S_i \leq S_{i+1} 对于所有人 i = 1, \ldots, N-1.
示例输入 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
示例输出 3
175
请注意,我们可能有 S_i = S_j 为 i \neq j.