I - Subsequence Pair Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MiB

問題文

N 個の文字列 S_1,\ldots,S_N が与えられます。

以下の条件をともに満たす整数の組 (i,j) の個数を求めてください。

  • 1 \leq i,j \leq N
  • S_i が S_j の部分列である
部分列とは 文字列の部分列とは、文字列から 0 個以上の位置の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことをいいます。 例えば、a, pe, apple は apple の部分列ですが、ea, hoge は違います。

制約

  • 1 \leq N \leq 10^5
  • N は整数
  • S_i は英小文字のみからなる長さが 1 以上 5 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S_1
\vdots
S_N

出力

答えを出力せよ。

入力例 1

3
ps
past
post

出力例 1

5

1 \leq i,j \leq N を満たす整数組 (i,j) は 9 個ありますが、そのうち以下の 5 個において S_i が S_j の部分列です。

  • (i,j)=(1,1)
  • (i,j)=(1,2)
  • (i,j)=(1,3)
  • (i,j)=(2,2)
  • (i,j)=(3,3)

入力例 2

5
a
aa
aaa
aaaa
aaaaa

出力例 2

15

入力例 3

2
hoge
hoge

出力例 3

4

Problem Statement

You are given N strings S_1,\ldots,S_N.

Find the number of integer pairs (i,j) such that:

  • 1 \leq i,j \leq N, and
  • S_i is a subsequence of S_j.
What is subsequence? A subsequence of a string is a string obtained by removing characters at zero or more positions and concatenating the remaining characters without changing their order. For example, a, pe, and apple are subsequences of apple, but ea and hoge are not.

Constraints

  • 1 \leq N \leq 10^5
  • N is an integer.
  • S_i is a string of length between 1 and 5, inclusive, consisting of lowercase English letters.

Input

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

N
S_1
\vdots
S_N

Output

Print the answer.

Sample Input 1

3
ps
past
post

Sample Output 1

5

Among nine pairs of integers (i,j) such that 1 \leq i,j \leq N, the following five satisfy the condition that S_i is a subsequence of S_j.

  • (i,j)=(1,1)
  • (i,j)=(1,2)
  • (i,j)=(1,3)
  • (i,j)=(2,2)
  • (i,j)=(3,3)

Sample Input 2

5
a
aa
aaa
aaaa
aaaaa

Sample Output 2

15

Sample Input 3

2
hoge
hoge

Sample Output 3

4