Minimum Color Ratio Subsequence

Bojan has noticed n cute, edible plush toys arranged on a shelf from position 1 to n. Each toy is painted in one of 26 colors, represented by lowercase English letters a to z.

For any contiguous set of toys, its color value is defined as \(\frac{d}{k}\), where \(d\) is the number of distinct colors in the subsequence and \(k\) is the total number of toys in that subsequence.

Bojan wants to eat a group of these toys, but he does not like too many colors. In other words, he wants to choose a contiguous subsequence of toys for which the color value \(\frac{d}{k}\) is minimized. If there are several answers, output the one which appears first.

Note: It is always valid to choose a subsequence consisting of a single toy (with color value 1). However, if there exists a contiguous block of toys having the same color, its color value \(\frac{1}{k}\) will be smaller for larger \(k\). Therefore, the problem essentially reduces to finding the longest contiguous subsequence of identical characters. If no subsequence of length greater than 1 exists, output any single toy.

inputFormat

The first line contains a single integer \(n\) (1 ≤ \(n\) ≤ 10⁵), the number of toys.

The second line contains a string of length \(n\) consisting of lowercase letters ('a' to 'z'), where the \(i\)th character represents the color of the \(i\)th toy.

outputFormat

Output two integers \(l\) and \(r\) (1-indexed), representing the starting and ending indices of the contiguous subsequence with the minimum color value. If there are multiple answers, output the one with the smallest starting index.

sample

5
ababa

1 1