题目描述

给定 $n$ 个仅由小写英文字母组成的字符串 $s_1,s_2,\dots,s_n$。

定义两个字符串 $a,b$ 的一次消去拼接 $F(a,b)$ 如下：

• 若 $a$ 为空串，则 $F(a,b)=b$；
• 若 $b$ 为空串，则 $F(a,b)=a$；
• 若 $a$ 的最后一个字符与 $b$ 的第一个字符相同，则同时删去这两个字符，并继续对剩余部分执行同样的操作；
• 否则操作停止，结果为当前 $a$ 与当前 $b$ 的直接拼接。

形式化地，若 $a$ 的最后一个字符等于 $b$ 的第一个字符，则会反复执行“删去 $a$ 的最后一个字符和 $b$ 的第一个字符”这一操作，直到某一侧为空，或这两个字符不再相同为止。

请你计算：

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\left|F(s_i,s_j)\right|.$$

其中 $\lvert x\rvert$ 表示字符串 $x$ 的长度。

输入格式

第一行输入一个整数 $n$（$1\le n\le 5\times 10^5$），表示字符串个数。

接下来 $n$ 行，每行输入一个非空字符串 $s_i$，只包含小写英文字母。

保证所有字符串长度之和不超过 $5\times 10^5$。

输出格式

输出一个整数，表示

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\left|F(s_i,s_j)\right|.$$

2
aba
ab

10