P7478 StickSuger

YSGHYYDS

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.

The first line contains a positive integer $n$, representing the length of the string $S$. The second line contains a string $S$.

If there is no solution, output `-1`. Otherwise, output two integers $i, j$ on one line, representing the largest valid ordered pair $(i, j)$.

**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