AT_arc175_f [ARC175F] Append Same Characters

给定 $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$

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

### 限制条件 - 输入的所有数值均为整数。 - $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 翻译