问题背景

本题中：

• 我们用 $|s|$ 表示字符串 $s$ 的前缀；
• 对于两个字符串 $a$ 和 $b$，我们用 $a + b$ 表示字符串拼接的结果，比如：
  • $\mathtt{'abc' + 'def' ='abcdef'}$
  • $\mathtt{'opq' + 'opq' = 'opqopq'}$

题目描述

对于一个字符串 $s$ 来说，如果它存在一个字符串 $t$ 同时满足如下条件：

• $1 \le |t| \lt s$；
• 字符串 $t$ 是字符串 $s$ 的前缀；
• 字符串 $s$ 是字符串 $t+t$ 的前缀。

则我们称字符串 $t$ 是字符串 $s$ 的一个 周期前缀。

我们称一个字符串的最长周期前缀长度为其所有周期前缀中最长的那个周期前缀的长度；特别地，如果一个字符串不包含任何周期前缀，则它的最长周期前缀长度为 $0$。

本题中，给你一个长度为 $n$ 的字符串 $s$，你需要求出 $s$ 的每一个非空前缀的最长周期前缀长度之和。

输入格式

第一行，一个整数 $n(1 \le n \le 10^6)$，表示字符串长度。

第二行，一个字符串 $s$。$s$ 仅由小写英文字母构成。

输出格式

输出一个整数，表示字符串 $s$ 的所有前缀的最长周期前缀长度之和。

样例

8
babababa

24

说明/提示

样例解释

字符串 $s = \mathtt{'babababa'}$，它的：

• 长度为 $1$ 的前缀为 $\mathtt{'b'}$，对应的最长非空前缀长度为 $0$；
• 长度为 $2$ 的前缀为 $\mathtt{'ba'}$，对应的最长非空前缀长度为 $0$；
• 长度为 $3$ 的前缀为 $\mathtt{'bab'}$，对应的最长非空前缀为 $\mathtt{'ba'}$，最长非空前缀长度为 $2$；
• 长度为 $4$ 的前缀为 $\mathtt{'baba'}$，对应的最长非空前缀为 $\mathtt{'ba'}$，最长非空前缀长度为 $2$；
• 长度为 $5$ 的前缀为 $\mathtt{'babab'}$，对应的最长非空前缀为 $\mathtt{'baba'}$，最长非空前缀长度为 $4$；
• 长度为 $6$ 的前缀为 $\mathtt{'bababa'}$，对应的最长非空前缀为 $\mathtt{'baba'}$，最长非空前缀长度为 $4$；
• 长度为 $7$ 的前缀为 $\mathtt{'bababab'}$，对应的最长非空前缀为 $\mathtt{'bababa'}$，最长非空前缀长度为 $6$；
• 长度为 $8$ 的前缀为 $\mathtt{'babababa'}$，对应的最长非空前缀为 $\mathtt{'bababa'}$，最长非空前缀长度为 $6$。

$0 + 0 + 2 + 2 + 4 + 4 + 6 + 6 = 24$。

数据规模与约定

• 对于 $30\%$ 的数据，$|s| \le 100$
• 对于 $60\%$ 的数据，$|s| \le 10^4$
• 对于 $100\%$ 的数据，$1 \le |s| \le 10^6$，字符串 $s$ 仅由小写英文字母构成