← 返回题目列表

Codeforces · 1043/G

G. 斑点带

中文机器翻译题面 查看原题

伊尔达拿了一条带子(一条细布)并给它上色。形式上,该带具有$$$n$$$个单元格,每个单元格都被着色为$$$26$$$颜色中的一种,因此我们可以用英文字母表中的一个小写字母来表示每种颜色。

Ildar 决定将乐队 $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$) 中他喜欢的部分从乐队中删除。因此,他将创建一个新的带,可以表示为字符串 $$$t = s_l s_{l+1} \ldots s_r$$$。

之后,Ildar 将玩以下游戏:他将乐队 $$$t$$$ 切割成一些新乐队,并计算其中不同乐队的数量。形式上,Ildar 选择 $$$1 \le k \le |t|$$$ 索引 $$$1 \le i_1 < i_2 < \ldots < i_k = |t|$$$ 并将 $$$t$$$ 切割为 $$$k$$$ band-strings $$$t_1 t_2 \ldots t_{i_1}, t_{i_1 + 1} \ldots t_{i_2}, \ldots, {t_{i_{k-1} + 1}} \ldots t_{i_k}$$$ 并计算其中不同波段的数量。他想知道在至少一个频段至少重复两次的约束下,他可以获得的不同频段的最小可能数量。游戏的结果就是这个数字。如果不可能以这种方式削减$$$t$$$,则游戏结果为-1。

不幸的是,Ildar 尚未决定他喜欢哪个片段,但他有 $$$q$$$ 片段候选者 $$$[l_1, r_1]$$$, $$$[l_2, r_2]$$$, ..., $$$[l_q, r_q]$$$。你的任务是计算他们每个人的游戏结果。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$) — Ildar 的带长度。

第二行包含一个字符串 $$$s$$$,由 $$$n$$$ 小写英文字母组成 - Ildar 的乐队。

第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 200\,000$$$) — Ildar 选择作为候选的段数。

接下来的 $$$q$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) 表示第 $$$i$$$ 段的结尾。

输出

输出 $$$q$$$ 行,其中第 $$$i$$$ 行应包含 $$$[l_i, r_i]$$$ 段上的游戏结果。

示例

输入 #1

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

输出 #1

1
-1
4
3
2
2
-1

注意

考虑第一个例子。

如果 Ildar 选择段 $$$[1, 6]$$$,他会剪切字符串 $$$t = abcabc$$$。如果他将 $$$t$$$ 切成两个带 $$$abc$$$ 和 $$$abc$$$,则带 $$$abc$$$ 会重复两次,不同磁带的数量为 $$$1$$$。所以,这场比赛的结果是$$$1$$$。

如果 Ildar 选择段 $$$[4, 7]$$$,他会剪切字符串 $$$t = abcd$$$。不可能以至少有一个带重复至少两次的方式来剪切该带。所以,这场比赛的结果是$$$-1$$$。

如果 Ildar 选择段 $$$[3, 6]$$$,他会剪切字符串 $$$t = cabc$$$。如果他将 $$$t$$$ 分成三个频段 $$$c$$$、$$$ab$$$ 和 $$$c$$$,则频段 $$$c$$$ 重复两次,不同频段的数量为 $$$2$$$。所以,这场比赛的结果是$$$2$$$。