Description

Bojan saw $n$ cute edible plush toys on a store shelf, numbered from $1$ to $n$. Each plush toy has one of $26$ different colors. Each color is represented by a lowercase English letter $a...z$.

For any set of toys, we define its “colorfulness” as the number of distinct colors in the set divided by the total number of toys in the set.

Bojan wants to eat these toys, but he does not like having too many colors. Please help Bojan find a contiguous subsequence of toys whose colorfulness is as small as possible.

Input Format

The first line contains a positive integer $n$, the number of toys.
The second line contains a string $S$ of length $n$, where the $i$-th character represents the color of the $i$-th toy on the shelf.

Output Format

Output a single line containing two integers $l, r$, the left and right endpoints of the required contiguous subsequence.
If there are multiple contiguous subsequences with the same (minimal) colorfulness, output any one of them.

4
honi

1 4

7
nivelle

4 7

6
ananas

1 5

Hint

Constraints and Notes

This problem uses bundled subtasks. There are 5 subtasks in total.

• Subtask 1 (7 points): $1 \leq n \leq 100$;
• Subtask 2 (17 points): $1 \leq n \leq 2 \times 10^3$;
• Subtask 3 (13 points): the string $S$ contains only two characters $a, b$ (you can think of it as there are only two colors in all toys).
• Subtask 4 (25 points): the string $S$ contains only five characters $a, b, c, d, e$ (you can think of it as there are only five colors in all toys).
• Subtask 5 (48 points): no special restrictions.

For all testdata, it is guaranteed that $1 \leq n \leq 10^5$ and $1 \leq l \leq r \leq n$.

[Hints and Help]

Translated from COCI 2019/2020 CONTEST #4 T5 Nivelle.

In COCI, this problem is worth $110$ points.

Translated by ChatGPT 5