Problem C: C 斑点带子

"
Time Limit $7$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $5$ 正确数量 $2$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

S拿了一条带子(一条薄布条)给它上色。正式地说,这个带子有n个单元格,每个单元格都被涂成26种颜色中的一种,所以我们可以用英文字母表中的一个小写字母来表示每种颜色。

S决定从他喜欢的带子的某个部分[l,r](1≤l≤r≤n)上取一些段[l,r],然后从带子上剪下来。因此,他将创建一个新的带子,可以表示为字符串t=slsl+1sr

在那之后,小S会玩下面的游戏:他把带子t切成一些新的带子,并计算其中不同带子的数量。在形式上,小S选择1≤k≤|t|索引 1i1<i2<…<ik<=|t|,t切成k个字符串 t1t2t3…..ti1,ti1+1……ti2,……,tik-1+1……tik 并计算其中不同带子的数目,他想知道在至少一个频带重复至少两次的约束下,他能得到的不同频带的最小可能数量。游戏的结果是这个数字。如果这样切t是不可能的,那么结果就是-1

不幸的是,小S还没有决定他喜欢哪一段,但他有q段供他选择,分别是  [l1,r1][l2,r2], ..., [lq,rq]。你的任务是计算每个游戏的结果。

第一行包含一个整数n(1≤n≤200000)——S带子的长度。

第二行包含一个由n个小写英文字母组成的字符串s

第三行包含一个整数q(1≤q≤200000)——S选择的段数。

接下来的q行每一行包含两个整数liri(1≤liri≤n),表示第i段的开始和结束。

输出q行,其中第i行应该包含段[li,ri]上的博弈结果。

9
abcabcdce
7
1 6
4 7
5 9
6 9
1 9
3 6
4 4
1
-1
4
3
2
2
-1

考虑第一个例子。

如果小S选择段[1,6],他将剪切一个字符串t=abcabc。如果他把t分成abcabc两个波段,abc波段重复两遍,不同磁带的数目是1。所以,这个博弈的结果是1

如果小S选择段[4,7],他将剪切一个字符串t=abcd。不可能以至少有一个频带重复至少两次的方式切割这个频带。这个博弈的结果是- 1

如果小S选择段[3,6],他将剪切一个字符串t=cabc。如果他把t分成cabc三个波段,c波段重复两次,不同波段的数目是2。所以,这个博弈的结果是2