Problem Description

YSGH gives you a string \( S \) of length \( n \). Let \( S_x \) denote the \( x \)-th character of string \( S \). You can choose a tuple \((i, j)\) and swap \( S_i \) and \( S_j \). The tuple \((i, j)\) is valid if and only if \( 1 \leq i < j \leq n \) and the lexicographical order of the resulting string is greater than the original string.

For two characters \( c_0 \) and \( c_1 \), \( c_0 > c_1 \) if and only if the ASCII value of \( c_0 \) is greater than that of \( c_1 \).

For two strings \( S \) and \( T \) of length \( n \), \( S \) is lexicographically greater than \( T \) if and only if there exists an \( i \in [0, n-1] \) such that \( \forall j \in [1, i], S_j = T_j \) and \( S_{i+1} > T_{i+1} \).

If there are multiple valid solutions, output the largest tuple.

For two tuples \((i_1, j_1)\) and \((i_2, j_2)\), \((i_1, j_1)\) is smaller than \((i_2, j_2)\) if and only if \( i_1 < i_2 \lor (i_1 = i_2 \land j_1 < j_2) \).

If there is no valid solution, output -1.

It is guaranteed that \( S \) contains only lowercase English letters.

Input Format

The first line contains a positive integer \( n \), the length of the string \( S \).

The second line contains the string \( S \).

Output Format

If there is no solution, output -1.

Otherwise, output two integers \( i \) and \( j \) representing the largest valid tuple \((i, j)\).

Sample Input and Output

Sample Input #1

3
acb

Sample Output #1

1 3

Sample Input #2

6
zyxwvu

Sample Output #2

-1

Sample Input #3

14
aabbccddccbbaa

Sample Output #3

6 8

Notes

[Sample Explanation #1]

If the tuple \((2, 3)\) is chosen, swapping \( S_2 \) and \( S_3 \) results in the string abc, which is lexicographically smaller than acb, so it is not valid.

If the tuple \((1, 3)\) is chosen, swapping \( S_1 \) and \( S_3 \) results in the string bca, which is lexicographically greater than acb, so it is valid.

Although \((1, 2)\) is also valid, it is not as large as \((1, 3)\). Therefore, the answer is \((1, 3)\).

[Sample Explanation #2]

It is easy to see that no tuple is valid.

[Data Range]

This problem is bundled test cases.

For \( 100\% \) of the data, \( 1 \leq n \leq 10^6 \), and \( S \) contains only lowercase English letters.

• Subtask 1 (4 points): \( S \) contains only one type of character.
• 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 \).

见题面 Input 部分

见题面 Output 部分