CF1043G Speckled Band

Ildar 拿了一条带子（一条细长的布条）并给它染上了颜色。形式上，这条带子有 $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$ 个带子字符串 $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 拥有的带子的长度。 第二行包含一个由 $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$ 个区间的左右端点。

输出 $q$ 行，第 $i$ 行输出第 $i$ 个区间的游戏结果。

考虑第一个样例。 如果 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$。 由 ChatGPT 4.1 翻译