Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
统计

题目描述

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$。