题目描述
Bojan 看到了 $n$ 个可爱的能吃的毛绒玩具摆在商店的货架上。从序号 $1$ 摆到 $n$。每个毛绒玩具都有 $26$ 中不同的颜色。每种颜色用英文字母 $a...z$ 表示。
Bojan 想吃这些玩具,但 Bojan 不喜欢有太多的颜色,所以请你帮助 Bojan 找到一个连续的子序列的玩具,使其不同的色彩数除以玩具数尽可能的少。
输入格式
第一行包含一个正整数 $n$,表示玩具的个数。
第二行包含长度为 $n$ 的字符串 $S$,第 $i$ 个字符表示架子上的第 $i$ 个玩具的颜色。
输出格式
输出只有一行,包含两个整数 $l,r$,表示所求连续子序列的左端点及右端点。
如果存在多个具有相同颜色数量且颜色最少的连续子序列,则输出任意一个子序列。
样例 #1
样例输入 #1
4
hoin
样例输出 #1
1 4
样例 #2
样例输入 #2
7
nivelle
样例输出 #2
4 7
样例 #3
样例输入 #3
6
ananas
样例输出 #3
1 5
提示
数据范围及约定
本题采用多测试点捆绑测试,共有 5 个子任务。
- 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):字符串 $S$ 中只有两个字符 $a,b$(你可以理解为所有玩具中只有两种颜色)。
- Subtask 4(25 points):字符串 $S$ 中只有五个字符 $a,b,c,d,e$(你可以理解为所有玩具中只有五种颜色)。
- Subtask 5(48 points):无特别限制。
对于全部的测试点,保证 $1 \leq n \leq 10^5,1 \leq l \leq r \leq n$。