CF1142B Lynyrd Skynyrd

*题目名称：Lynyrd 与 Skynyrd* 最近 Lynyrd 和 Skynyrd 去了一个商店，在那里 Lynyrd 买了一个长度为 $n$ 的排列 $p$，Skynyrd 买了一个一个长度为 $m$ 的数列 $a$，并且 $a_i \in[1,n], a_i \in Z$。 Lynyrd 和 Skynyrd 感到无聊，所以他们给了你 $q$ 个询问，每个询问格式如同：“ $a$ 的**子段** $[l, r]$ 是否有一个**子序列** $s$，满足 $s$ 是 $p$ 的一个循环移位？”请你回答这些询问。 一个长度为 $n$ 的*排列*是一个由 $n$ 个整数组成的序列，满足从 $1$ 到 $n$ 的所有整数在其中恰好出现 $1$ 次。 一个排列 $(p_1, p_2, \ldots, p_n)$ 的*循环移位*是排列 $(p_i, p_{i+1}, \ldots, p_n, p_1, p_2, \ldots, p_{i-1})$，其中 $i \in [1, n]$。例如： $(2, 1, 3)$ 有 3 个显然的循环移位：$(2, 1, 3); (1, 3, 2); (3, 2, 1)$。 一个序列 $a$ 的子段 $[l, r]$ 的*子序列*是一个序列 $a_{i_1}, a_{i_2}, \ldots a_{i_k}$，其中 $l \leq i_1 < i_2 < \ldots < i_k \leq r$。

输入文件的第一行包含三个整数 $n, m, q \ (1 \leq n, m, q \leq 2 \times 10^5)$ —— 排列 $p$ 的长度，序列 $a$ 的长度和询问的个数。 接下来一行包含 $n$ 个整数，第 $i$ 个整数表示排列 $p$ 的元素 $p_i$。保证 $[1, n]$ 中的每个整数恰好出现 $1$ 次。 接下来一行包含 $m$ 个整数，第 $i$ 个整数表示数列 $a$ 的元素 $a_i$。保证 $a_i \in [1, n]$。 接下来 $q$ 行每行描述一组询问。这 $q$ 行中的第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ $(1 \leq l_i \leq r_i \leq m)$，表示第 $i$ 个询问是关于 $a$ 的子段 $[l, r]$ 的。

输出文件仅包含一个由 `0` 或 `1` 组成的长度为 $q$ 的字符串，字符串的第 $i$ 位表示第 $i$ 次询问的结果：`0` 表示不存在，`1` 表示存在。

样例 1 中子段 $[1, 5]$ 是 $\underline1, 2, \underline3, 1, \underline2$，它包含的一个子序列 $1, 3, 2$ 是给定排列的一个循环移位；子段 $[2, 6]$ 包含的子序列 $2, 1, 3$ 与给定排列等价；子段 $[3, 5]$ 只有一个长度为 $3$ 的子序列 $3, 1, 2$，但是这不是给定序列的循环移位。 样例 2 中所有可能的循环移位是 $1, 2$ 和 $2, 1$。子段 $[1, 2]$ 是 $1, 1$，不包含任何循环移位；子段 $[2, 3]$ 是 $1, 2$，是一个循环移位；子段 $[3, 4]$ 是 $2, 2$，它的所有子段中没有一个是给定排列的循环移位。