当你出不来题，就在以前出过的题上面魔改。——《鲁迅说的》

称一个串为”反回文串“当且仅当其反转之后和原串每一位都不同。如：“0101” 是”反回文串“，“120212”是”反回文串“，“01010110”不是”反回文串“。
不难发现，反回文串的长度必须是偶数。定义一个反回文串的“回文中心”为其最中间两个字符之间的缝隙，一个“回文中心”的”反回文半径“为以它为“回文中心”的最长”反回文串“长度的一半。
给定一个长度为 $n$ 的三进制数字串（只包含 ’0‘,'1','2'）的字符串。请你对于 $n-1$ 个”回文中心“分别求出其 “反回文半径”。

输入格式

第一行一个数字 $n$ 表示字符串的长度。

第二行一个长度为 $n$ 的字符串。

输出格式

一行 $n-1$ 个数字，第 $i$ 个数字表示以第 $i$ 个和 第 $i+1$ 个字符之间的缝隙作为“回文中心”的“反回文半径“。

样例1

输入

10
0102012011

输出

1 2 3 3 1 1 1 2 0

数据规模

subtask1(20pts) : $n\le 10000$。

subtask2(20pts)：$n\le 100000$。

subtask3(20pts)：$n\le 200000$，且保证字符串只包含 '0','1'；

subtask4(40pts)：$n\le 200000$。