CF1043G.Speckled Band

Ildar took a band (a thin strip of cloth) and colored it. Formally, the band has $n$ cells, each of them is colored into one of $26$ colors, so we can denote each color with one of the lowercase letters of English alphabet.

Ildar decided to take some segment of the band $[l, r]$ ($1 \le l \le r \le n$) he likes and cut it from the band. So he will create a new band that can be represented as a string $t = s_l s_{l+1} \ldots s_r$.

After that Ildar will play the following game: he cuts the band $t$ into some new bands and counts the number of different bands among them. Formally, Ildar chooses $1 \le k \le |t|$ indexes $1 \le i_1 \lt i_2 \lt \ldots \lt i_k = |t|$ and cuts $t$ to $k$ bands-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}$ and counts the number of different bands among them. He wants to know the minimal possible number of different bands he can get under the constraint that at least one band repeats at least two times. The result of the game is this number. If it is impossible to cut $t$ in such a way, the result of the game is -1.

Unfortunately Ildar hasn't yet decided which segment he likes, but he has $q$ segments-candidates $[l_1, r_1]$, $[l_2, r_2]$, ..., $[l_q, r_q]$. Your task is to calculate the result of the game for each of them.

伊尔达尔取了一条带子（一条细长的布条）并给它染色。形式化地说，这条带子有 $n$ 个格子，每个格子被染成 $26$ 种颜色之一，因此我们可以用英文字母表中的一个小写字母来表示每种颜色。

伊尔达尔决定选取他喜欢的带子上某个区间 $[l, r]$（其中 $1 \le l \le r \le n$）并将该区间从原带子上剪下。于是他将得到一条新带子，可表示为字符串 $t = s_l s_{l+1} \ldots s_r$。

之后，伊尔达尔将进行如下游戏：他将带子 $t$ 切割成若干新的带子，并统计其中互不相同的带子的数量。形式化地说，伊尔达尔选择 $1 \le k \le |t|$ 个下标 $1 \le i_1 \lt i_2 \lt \ldots \lt i_k = |t|$，将 $t$ 切割为 $k$ 条子带（即子字符串）：
$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$。

遗憾的是，伊尔达尔尚未确定他究竟喜欢哪一段，但他已有 $q$ 个候选区间：$[l_1, r_1]$、$[l_2, r_2]$、…、$[l_q, r_q]$。你的任务是对每个候选区间，计算对应的游戏结果。

The first line contains one integer $n$ ($1 \le n \le 200\,000$) — the length of the band Ildar has.

The second line contains a string $s$ consisting of $n$ lowercase English letters — the band Ildar has.

The third line contains a single integer $q$ ($1 \le q \le 200\,000$) — the number of segments Ildar has chosen as candidates.

Each of the next $q$ lines contains two integer integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) denoting the ends of the $i$-th segment.

第一行包含一个整数 $n$（$1 \le n \le 200\,000$）—— 表示 Ildar 所拥有的带子的长度。

第二行包含一个由 $n$ 个小写英文字母组成的字符串 $s$ —— 表示 Ildar 所拥有的带子。

第三行包含一个整数 $q$（$1 \le q \le 200\,000$）—— 表示 Ildar 所选出的候选区间的数量。

接下来的 $q$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 个区间的左右端点。

Output $q$ lines, where the $i$-th of them should contain the result of the game on the segment $[l_i, r_i]$.

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

Consider the first example.

If Ildar chooses the segment $[1, 6]$, he cuts a string $t = abcabc$. If he cuts $t$ into two bands $abc$ and $abc$, the band $abc$ repeats two times and the number of different tapes is $1$. So, the result of this game is $1$.

If Ildar chooses the segment $[4, 7]$, he cuts a string $t = abcd$. It is impossible to cut this band in such a way that there is at least one band repeating at least two times. So, the result of this game is $-1$.

If Ildar chooses the segment $[3, 6]$, he cuts a string $t = cabc$. If he cuts $t$ into three bands $c$, $ab$ and $c$, the band $c$ repeats two times and the number of different bands is $2$. So, the result of this game is $2$.

考虑第一个例子。

如果伊尔达尔选择区间 $[1, 6]$，他将截取字符串 $t = abcabc$。若将 $t$ 切割成两个条带 $abc$ 和 $abc$，则条带 $abc$ 重复了两次，且不同条带的数量为 $1$。因此，该轮游戏的结果为 $1$。

如果伊尔达尔选择区间 $[4, 7]$，他将截取字符串 $t = abcd$。此时无法以某种方式切割该条带，使得至少有一个条带重复出现至少两次。因此，该轮游戏的结果为 $-1$。

如果伊尔达尔选择区间 $[3, 6]$，他将截取字符串 $t = cabc$。若将 $t$ 切割成三个条带 $c$、$ab$ 和 $c$，则条带 $c$ 重复了两次，且不同条带的数量为 $2$。因此，该轮游戏的结果为 $2$。