伊尔达拿了一条带子(一条细布)并给它上色。形式上,该带具有$$$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$$$。