题目描述

高中生物中提到，酶切位点 是基因序列上一段特定的碱基序列，而 限制性核酸内切酶 能够识别出这个序列并在对应的切割位置将基因序列切成两段。

现有一种名为 $\texttt{EcoRI}$ 的限制酶，其识别序列为 GAATTC，切割位置在 G 和 A 之间。

给出一段长度为 $n$ 的基因序列（仅由 A/T/G/C 组成的字符串），请你判断使用 $\texttt{EcoRI}$ 在理想条件下能将此序列切成几个部分，并输出每个切割位置 左侧 碱基的下标。

定义该基因序列的下标从左到右分别为 $1, 2, 3, \dots, n$。

输入格式

第 $1$ 行一个正整数 $n$ 表示基因序列长度。

第 $2$ 行一个长度为 $n$ 的字符串表示基因序列，保证只出现 A/T/G/C 四种字符。

输出格式

第 $1$ 行输出一个正整数 $x$，表示 $\texttt{EcoRI}$ 在理想条件下能将给出序列切成 $x$ 个部分。

第 $2$ 行从小到大输出 $x-1$ 个正整数，表示每个切割位置 左侧 碱基的下标。

样例输入

15
GATCGGAATTCTTCA

样例输出

2
6

样例说明

显然，对于此样例，容易找到 $\texttt{EcoRI}$ 的识别序列和切割位点：$\texttt{GATCG}\color{red}{\texttt{G↓AATTC}}\texttt{TTCA}$。

所以，可以将原基因序列切割成 $2$ 部分，切割位置左侧碱基 G 的下标为 $6$。

数据范围

$6 \le n \le 10^7$

其实就是个 KMP 板子题，已经不能再板子了。（如果不能理解题面，可以看样例说明）