CF1131E String Multiplication

Roman 和 Denis 正在前往编程比赛的旅途中。由于旅途漫长，他们很快就感到无聊，于是决定想点新花样。Roman 发明了一种披萨的做法，而 Denis 则发明了一种字符串乘法。根据 Denis 的定义，长度为 $m$ 的字符串 $s$ 与字符串 $t$ 的乘积（即 $s \cdot t$）是一个新字符串，其形式为 $t + s_1 + t + s_2 + \ldots + t + s_m + t$，其中 $s_i$ 表示字符串 $s$ 的第 $i$ 个字符，"+" 表示字符串拼接。例如，字符串 "abc" 和 "de" 的乘积为 "deadebdecde"，而字符串 "ab" 和 "z" 的乘积为 "zazbz"。注意，与数字的乘法不同，字符串 $s$ 与 $t$ 的乘积不一定等于 $t$ 与 $s$ 的乘积。 Roman 对 Denis 的这个有趣操作感到有些嫉妒，于是他也想发明点与字符串相关的东西。Roman 是个美感爱好者，他定义字符串的“美丽值”为其中只包含同一个字母的最长连续子串的长度。例如，字符串 "xayyaaabca" 的美丽值为 $3$，因为有子串 "aaa"；而字符串 "qwerqwer" 的美丽值为 $1$，因为其中所有相邻字符都不相同。 为了娱乐 Roman，Denis 在纸上写下了 $n$ 个字符串 $p_1, p_2, p_3, \ldots, p_n$，并让 Roman 计算字符串 $((\ldots(((p_1 \cdot p_2) \cdot p_3) \cdot \ldots ) \cdot p_n)$ 的美丽值（其中 $s \cdot t$ 表示字符串 $s$ 与 $t$ 的乘积）。Roman 还没完全理解 Denis 的字符串乘法，于是向你寻求帮助。Denis 知道 Roman 很容易被震撼，他保证最终结果的美丽值不会超过 $10^9$。

第一行包含一个整数 $n$（$2 \leq n \leq 100\,000$），表示 Denis 写下的字符串数量。 接下来的 $n$ 行，每行一个非空字符串 $p_1, p_2, \ldots, p_n$，均由小写英文字母组成。 保证所有字符串的总长度不超过 $100\,000$，且最终乘积字符串的美丽值不超过 $10^9$。

输出一个整数，表示最终乘积字符串的美丽值。

在第一个样例中，字符串的乘积为 "abaaaba"。 在第二个样例中，字符串的乘积为 "abanana"。 由 ChatGPT 4.1 翻译