#P18735. [正睿NOI2021训练] 数据结构

[正睿NOI2021训练] 数据结构

数据结构

给定一个仅包含小写英文字母的字符串 SS。

对于两个非空字符串 A,BA,B,称 BB“跟随”AA,当且仅当:

  1. ABAB 是 SS 的一个子串。
  2. 对 AA 在 SS 中的每一次出现,若该次出现之后至少还剩 ∣B∣|B| 个字符,则紧接着的 ∣B∣|B| 个字符必须组成 BB;若剩余字符不足 ∣B∣|B|,则这次出现不施加要求。

求满足上述条件的有序字符串对 (A,B)(A,B) 的数量,其中 A,BA,B 都必须是 SS 的非空子串。按字符串内容区分,不按出现位置区分。不同位置的出现可以相互重叠。

输入格式

第一行一个正整数 nn;第二行一个长度为 nn 的字符串 SS。

输出格式

输出一个整数,表示符合要求的有序字符串对数量。

数据范围

1≤n≤2000001\le n\le200000,SS 仅含小写英文字母。

样例 1

输入

4
aabc

输出

6

样例 2

输入

7
abacaba

输出

44