Problem Description

Bojan sees \( n \) cute, edible plush toys arranged on a store shelf, numbered from 1 to \( n \). Each plush toy has one of 26 different colors, represented by the letters \( a \) to \( z \).

For any set of toys, we can define its color diversity 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 dislikes having too many colors. Therefore, please help Bojan find a continuous subsequence of toys with the least color diversity.

Input Format

The first line contains a positive integer \( n \), representing 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 \) and \( r \), representing the left and right endpoints of the desired continuous subsequence.
If there are multiple continuous subsequences with the same minimum color diversity, output any one of them.

Sample Input and Output

Sample Input #1

4
hoin

Sample Output #1

1 4

Sample Input #2

7
nivelle

Sample Output #2

4 7

Sample Input #3

6
ananas

Sample Output #3

1 5

Notes/Hints

Data Range and Constraints

This problem uses multiple test cases bundled together, with a total of 5 subtasks.

• 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 \) and \( b \) (you can consider that all toys have only two colors).
• Subtask 4 (25 points): The string \( S \) contains only five characters \( a, b, c, d, e \) (you can consider that all toys have only five colors).
• Subtask 5 (48 points): No special restrictions.

For all test cases, it is guaranteed that \( 1 \leq n \leq 10^5 \) and \( 1 \leq l \leq r \leq n \).

Translated from COCI 2019/2020 CONTEST #4 T5 Nivelle

In COCI, this problem is worth \( 110 \) points.

见题面 Input 部分

见题面 Output 部分