时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 1024 M,其他语言2048 M
64bit IO Format: %lld
题目描述
给你一个长度为

的小写字母串

,请你对所有的右端点

,计算出最小的左端点

,满足反转

中左端点为

且右端点为

的子串得到字符串

后,

的字典序严格大于

,特别地,当右端点

不存在一个符合条件的左端点

时,输出

。
【反转】
反转就是将字符串从右往左重新书写,例如

反转后得到

。
【子串】子串为从原字符串中,连续的选择一段字符(可以全选、可以不选)得到的新字符串。
【广义的字典序比较】从字符串的第一个字符开始逐个比较,直到找到第一个不同的位置,通过比较这个位置字符的

码大小得到字符串的大小,称为
字典序比较。例如,字符串

和

比较时,由于第一个字符不相同,所以

。
输入描述:
第一行输入一个正整数,表示
)
。
第二行输入一个长度为

的小写字母串,表示

。
输出描述:
第一行输出
个整数,第
个整数表示右端点为
时的答案。
示例1
说明
对于右端点
,有 