Description

YSGH gives you a string $S$ of length $n$. Let $S_x$ denote the $x$-th character of the string $S$. You may choose an ordered pair $(i, j)$ and then swap $S_i$ and $S_j$. The pair $(i, j)$ is valid if and only if $1 \le i < j \le n$ and the string after the swap is lexicographically greater than the original string.

For two characters $c_0, c_1$, we say $c_0 > c_1$ if and only if the ASCII code of $c_0$ is greater than that of $c_1$.

For two strings $S, 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 ordered pair.

For two ordered pairs $(i_1, j_1)$ and $(i_2, j_2)$, we say $(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$, representing the length of the string $S$.

The second line contains a string $S$.

Output Format

If there is no solution, output -1.

Otherwise, output two integers $i, j$ on one line, representing the largest valid ordered pair $(i, j)$.

3
acb

1 3

6
zyxwvu

-1

14
aabbccddccbbaa

6 8

Hint

Sample Explanation #1

If you choose the ordered pair $(2, 3)$, after swapping $S_2$ and $S_3$ the string becomes abc, which is lexicographically smaller than acb, so it is invalid.

If you choose the ordered pair $(1, 3)$, after swapping $S_1$ and $S_3$ the string becomes bca, which is lexicographically greater than acb, so it is valid.

Although $(1, 2)$ is also valid, it is not larger than $(1, 3)$. Therefore, the answer is $(1, 3)$.

Sample Explanation #2

It is easy to see that any ordered pair is invalid.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le n \le 10^6$, and $S$ contains only lowercase English letters.

• Subtask 1 (4 points): $S$ contains only one distinct character.
• Subtask 2 (10 points): $n \le 100$.
• Subtask 3 (16 points): $n \le 500$.
• Subtask 4 (25 points): $n \le 5000$.
• Subtask 5 (18 points): $n \le 10^5$.
• Subtask 6 (27 points): $n \le 10^6$.

Translated by ChatGPT 5