题目内容

当日，小红薯翻开小红书后看到一则每日一题里的编程题，内容是:

[引用开始]

把首尾两个字母相同的串叫做闭环串。

问：在某个串的所有连续片段里，有几段并不属于闭环串。

[引用结束]

碰巧，这两日小红薯正补字符串方面的功课，这类串在工程里到处都能见到，因此得踏实掌握。

小红薯在评论区又见到该问法的加强版:给定字符序列$w_1,w_2..w_m$,对每一个前缀$[1]$按顺序分别计算，它的全部非空连续片段$[2]$里有几段并不属于闭环串。

小红薯感到这道题挺好玩，于是动手写代码来把它做掉。

[名词解释]

前缀$[1]$:自原串最左侧那个字符起，不间断地取若干字符拼成的新串。长度记为 $m$ 的串一共有 $m$ 个互不相同的前缀。

子串$[2]$:自原串里不间断地切出一段字符(允许整段都取)得到的新串。

输入描述

第一行读入一个整数$m(1≤m≤2×10^5)$代表串有多长。

第二行读入一个长度是$m$，全由小写英文字母构成的串$w$。

输出描述

总共$m$行，第$k$行写出一个整数，代表原串前缀片段$[1,k]$里全部连续片段中，不属于闭环串的个数。

样例1

输入

4
cabd

输出

0
1
3
6

说明

看前缀片段$[1,3]$也就是"$cab$"，它的全部连续片段是"$c$"，"$a$"，"$b$"，"$ca$"，"$ab$","$cab$"，前三段属于闭环串,后三段不是。