字符串
时间限制：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{