双频信号片段 (dual_frequency_segments)

题目描述

通信实验室记录了一段只包含两种频率的信号，用字符 A 和 B 表示。工程师要从这段记录中截取连续片段，判断片段内部是否足够“稳定”。

稳定性的判定来自一个对称性规则：片段里的每个位置，都必须落在片段内部某个长度大于 $1$ 的回文连续子串中。

对于一个长度大于 $1$ 的连续子串 $S$：

• 如果 $S$ 中每个字符都能被 $S$ 内某个长度大于 $1$ 的回文子串覆盖，则它是稳定片段；
• 否则它是不稳定片段。

这里“覆盖”的含义是：对 $S$ 中的每个位置，都存在一个属于 $S$ 的回文连续子串，长度大于 $1$，并且该回文子串包含这个位置。

请输出稳定片段数量和不稳定片段数量。

输入格式

在文件 dual_frequency_segments.in 中读入。 第一行一个整数 $n$，满足 $1 \le n \le 3\times 10^5$。 第二行一个长度为 $n$ 的字符串，只包含字符 A 和 B。

输出格式

在文件 dual_frequency_segments.out 中输出。 输出两个整数，分别表示稳定片段数量和不稳定片段数量。

样例

输入数据1

5
AABAA

输出数据1

6 4

提示

数据范围与提示