AT1202Contest_e Half Palindromes

给定一个由小写英文字母组成的字符串 $ S $。对于 $ S $ 的所有连续子串，共有 $ \lceil \lvert S \rvert \div 2 \rceil$ 个，针对每个子串解决以下问题，并求解所有解的总和。 问题：给定一个由小写英文字母组成的字符串 $ T $。请找出 $ T $ 可以通过以下操作任意多次得到的最小长度。 - 操作：从 $ T $ 的前缀中选择一个奇数长度的回文串（假设长度为 $ 2k+1 $），删除 $ T $ 的前 $ k $ 个字符。

从标准输入中给出输入，具有以下格式： > $ S $

输出答案。 ### 约束 - $ 1 \leq \lvert S \rvert \leq 10^6 $ - $ S $ 由小写英文字母组成 Translate by [@XYQ_102](https://www.luogu.com.cn/user/712337)

### 制約 - $ 1\leq\ |S|\leq\ 10^6 $ - $ S $ は英小文字からなる ### Sample Explanation 1 $ T $ が `a` または `b` のとき，答えは $ 1 $ です． $ T $ が `ab` または `ba` のとき，答えは $ 2 $ です． $ T $ が `aba` または `bab` のとき，$ k=1 $ として操作を一度行うのが最適であり，答えは $ 2 $ です． $ T $ が `abab` のとき，$ k=1 $ として操作を行ったあと，もう一度 $ k=1 $ として操作を行うのが最適であり，答えは $ 2 $ です． よって全体の答えは $ 1\times\ 4\ +\ 2\times\ 3\ +\ 2\times\ 2\ +\ 2\times\ 1\ =\ 16 $ です．