字符串
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld

题目描述

给你一个长度为 n 的小写字母串 s,请你对所有的右端点 1 \leq r \leq n,计算出最小的左端点 1 \leq l \leq r,满足反转 s 中左端点为 l 且右端点为 r 的子串得到字符串 t 后,t 的字典序严格大于 s,特别地,当右端点 r 不存在一个符合条件的左端点 l 时,输出 -1

【反转】反转就是将字符串从右往左重新书写,例如 s_1s_2\dots s_n 反转后得到 s_n s_{n-1} \dots s_1
【子串】子串为从原字符串中,连续的选择一段字符(可以全选、可以不选)得到的新字符串。
【广义的字典序比较】从字符串的第一个字符开始逐个比较,直到找到第一个不同的位置,通过比较这个位置字符的 \sf Ascii 码大小得到字符串的大小,称为字典序比较。例如,字符串 \texttt{
\texttt{ 比较时,由于第一个字符不相同,所以 \texttt{

输入描述:

第一行输入一个正整数,表示 n\ (1 \leq n \leq 4\cdot10^5)
第二行输入一个长度为 n 的小写字母串,表示 s_1,s_2,\cdots,s_n

输出描述:

第一行输出 n 个整数,第 i 个整数表示右端点为 i 时的答案。
示例1

输入

复制
10
eabaabacde

输出

复制
-1 -1 2 -1 -1 2 4 2 2 1

说明

对于右端点 r = 3,有 \texttt{