#3245. 「COCI 2020.1」Nivelle

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: HeRaNO

题目描述

译自 COCI 2019/2020 Contest #4 T5「Nivelle」

原本的题目描述由于过于暴力而被修改。下面的程序适合于初级选手。

Bojan 看见了货架上摆着 N 个可爱的,毛绒绒的并且还能吃的小玩具(yaay),它们按从 1 N 的顺序排列。每个毛绒玩具用 26 种不同的颜色之一染色。每种颜色用一个小写的英文字母表示。Bojan 想要吃掉其中的一些(流口水)。

对于任意的玩具集合,我们定义它的多彩值为集合内玩具的不同颜色数与集合内玩具数量的比值。Bojan 讨厌多彩,同时他也很饿。他想要吃掉一个连续子序列的玩具。

请帮助 Bojan 找到一个多彩值最小的连续子序列。

输入格式

第一行包含一个整数 N ,表示玩具个数;

第二行包含一个长为 N 的字符串 S ,第 i 个字符表示货架上第 i 个玩具的颜色。

输出格式

输出两个正整数 L,R\ (1\le L\le R\le N) ,表示所求的连续子序列是 L,L+1,\ldots ,R

如果有多个满足条件的连续子序列,输入任意一个均可。

样例

样例输入 1

4
honi

样例输出 1

1 4

样例输入 2

7
nivelle

样例输出 2

4 7

样例输入 3

6
ananas

样例输出 3

1 5

数据范围与提示

对于全部数据, 1\le N\le 10^5 ,保证 S 中只出现小写英文字母。

详细子任务附加限制及分值如下表:

子任务编号 附加限制 分值
1 N\le 100 6
2 N\le 2\times 10^3 15
3 S 中只包含 \texttt{'a', 'b'} 12
4 S 中只包含 \texttt{'a', 'b', 'c', 'd', 'e'} 23
5 无附加限制 44