| 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+1…sr。
在那之后，小S会玩下面的游戏:他把带子t切成一些新的带子，并计算其中不同带子的数量。在形式上，小S选择1≤k≤|t|索引 1≤i1<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行每一行包含两个整数li和ri(1≤li≤ri≤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分成abc和abc两个波段，abc波段重复两遍，不同磁带的数目是1。所以，这个博弈的结果是1。
如果小S选择段[4,7]，他将剪切一个字符串t=abcd。不可能以至少有一个频带重复至少两次的方式切割这个频带。这个博弈的结果是- 1。
如果小S选择段[3,6]，他将剪切一个字符串t=cabc。如果他把t分成c、ab和c三个波段，c波段重复两次，不同波段的数目是2。所以，这个博弈的结果是2。