/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
英小文字からなる N 個の文字列 S_1, \dots, S_N が与えられます．以下の 2 種類の操作を好きな順番で 0 回以上好きな回数行うことを考えます．
- 英小文字 c を 1 つ選ぶ．全ての 1 \leq i\leq N について，S_i の末尾に c を追加する．
- 1 \leq i \leq N-1 を満たす整数 i を 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 が存在して，下記の 2 つがともに成り立つ．
- 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 行に出力せよ．
入力例 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) となる．このとき全ての i = 1, \ldots, N-1 について S_i \leq S_{i+1} が満たされている．
3 回未満の操作により，全ての i = 1, \ldots, N-1 について S_i \leq S_{i+1} が満たされている状態にすることはできないので，3 を出力します．
入力例 2
3 kitekuma nok zkou
出力例 2
0
操作を行う前の時点で，全ての i = 1, \ldots, N-1 について S_i \leq S_{i+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
i \neq j に対して S_i = S_j となりうることに注意してください．
Score: 1000 points
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.
- |S| \lt |T| and S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
- 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
zto 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.