Score: $500$ points

问题陈述

对于字符串 $x$ 和 $y$，定义 $f(x, y)$ 如下：

• $f(x, y)$ 是 $x$ 和 $y$ 的最长公共前缀的长度。

给定由小写英文字母组成的 $N$ 个字符串 $(S_1, \ldots, S_N)$。找出以下表达式的值：

$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i,S_j)$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

For strings $x$ and $y$, define $f(x, y)$ as follows:

• $f(x, y)$ is the length of the longest common prefix of $x$ and $y$.

You are given $N$ strings $(S_1, \ldots, S_N)$ consisting of lowercase English letters. Find the value of the following expression:

$\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i,S_j)$.

Constraints

• $2 \leq N \leq 3\times 10^5$
• $S_i$ is a string consisting of lowercase English letters.
• $1 \leq |S_i|$
• $|S_1|+|S_2|+\ldots+|S_N|\leq 3\times 10^5$
• All input numbers are integers.

Input

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

$N$

$S_1$ $\ldots$ $S_N$

Output

Print the answer.

Sample Input 1

3
ab abc arc

Sample Output 1

4

• $f(S_1,S_2)=2$
• $f(S_1,S_3)=1$
• $f(S_2,S_3)=1$

Thus, the answer is $f(S_1,S_2) + f(S_1,S_3) + f(S_2,S_3) = 4$.

Sample Input 2

11
ab bb aaa bba baba babb aaaba aabbb a a b

Sample Output 2

32