题目背景

YSGHYYDS

题目描述

YSGH 给你一个长度为 $n$ 的字符串 $S$。设 $S_x$ 表示字符串 $S$ 的第 $x$ 个字符。你可以选择一个二元组 $(i,j)$，然后交换 $S_i$ 和 $S_j$。二元组 $(i,j)$ 是合法的当且仅当 $1\leq i<j\leq n$ 并且交换后的字符串的字典序比原串大。

对于两个字符 $c_0,c_1$，称 $c_0>c_1$ 当且仅当 $c_0$ 的 ASCII 码大于 $c_1$ 的 ASCII 码。

对于两个长度为 $n$ 的字符串 $S,T$，$S$ 的字典序大于 $T$ 当且仅当存在一个 $i\in [0,n-1]$ 使得 $\forall j\in[1,i],S_j=T_j$， 并且 $S_{i+1}>T_{i+1}$。

如果存在多种合法方案，输出最大的二元组。

对于两个二元组 $(i_1,j_1)$，$(i_2,j_2)$，称 $(i_1,j_1)$ 小于 $(i_2,j_2)$ 当且仅当 $i_1<i_2\lor(i_1=i_2\land j_1<j_2)$。

如果不存在合法方案，则输出 -1。

保证 $S$ 只包含小写英文字母。

输入格式

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

第二行，一个字符串 $S$。

输出格式

如果无解，输出 -1。

否则一行输出两个整数 $i,j$ 表示最大的合法二元组 $(i,j)$。

3
acb

1 3

6
zyxwvu

-1

14
aabbccddccbbaa

6 8

提示

【样例解释 #1】

如果选择二元组 $(2,3)$，交换 $S_2$ 和 $S_3$ 后的字符串为 abc，字典序比 acb 小，所以不合法。

如果选择二元组 $(1,3)$，交换 $S_1$ 和 $S_3$ 后的字符串为 bca，字典序比 acb 大，是合法的。

虽然 $(1,2)$ 也是合法的，但是没有 $(1,3)$ 大。所以答案是 $(1,3)$。

【样例解释 #2】

容易看出任何一个二元组都不合法。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$S$ 只包含小写英文字母。

• Subtask 1（4 points）：$S$ 只包含一种字符。
• Subtask 2（10 points）：$n\leq 100$。
• Subtask 3（16 points）：$n\leq 500$。
• Subtask 4（25 points）：$n\leq 5000$。
• Subtask 5（18 points）：$n\leq 10^5$。
• Subtask 6（27 points）：$n\leq 10^6$。