题目内容

在一条直线上摆放着 $n$ 个独立的容器，从左到右依次编号为 $1$ 到 $n$。初始时，每个容器内装有一种独一无二的试剂，第 $i$ 个容器的试剂编号为 $i$。

接下来会进行 $t$ 次实验，按顺序编号为 $1$ 到 $t$。第 $k$ 次实验时，科学家选择一个位置 $p$ ($1 \le p \le n-1$)，并观察容器 $p$ 和 $p+1$ 中的试剂是否已经属于同一个试剂族群。若它们当前不属于同一族群，则将两个族群合并为一个新的试剂族群，并记录这次合并发生的时间为 $k$；若它们已经属于同一族群，则本次实验不会产生任何改变。 最初，每个容器自成一个族群。一次合并操作会将两个被选位置所在的整个族群合并（包含族群中所有的容器）。 对于给定的询问区间 $[l, r]$，请找出最早的实验时刻（允许是第 $0$ 次实验开始之前，即初始状态），使得位置 $l$ 到 $r$ 的所有容器中的试剂全部属于同一个族群。如果直到 $t$ 次实验全部结束后仍未满足，则输出 $-1$。

约束:

• $n$, $t$, $q$ 均不超过 $2 \times 10^5$。
• 每次实验的 $p$ 满足 $1 \le p \le n-1$。
• 每个询问的 $l$, $r$ 满足 $1 \le l \le r \le n$。

输入描述

第一行包含三个整数 $n, t, q$。接下来的 $t$ 行，第 $k$ 行包含一个整数 $p$，表示第 $k$ 次实验选择的位置。再接下来的 $q$ 行，每行包含两个整数 $l, r$，表示一次询问。

输出描述

对于每个询问，输出一行一个整数，表示最早满足条件的时刻（从 $0$ 开始），若不存在则输出 $-1$。

样例1

输入

3 2 4
1
2
1 2
2 3
1 3
1 1

输出

1
2
2
0

说明

初始时，容器 1、2、3 各自独立。

第 1 次实验选择位置 $p=1$，容器 1 和 2 合并为一个族群，合并时间记录为 1。此时询问 $[1,2]$ 的最早满足时间为 1。

第 2 次实验选择 $p=2$，此时容器 2 所在的族群（包含 1 和 2）与容器 3 合并，合并时间记录为 2。这使得容器 2 和 3（询问 $[2,3]$）以及 1 和 3（询问 $[1,3]$）都在时刻 2 首次属于同一族群。

询问 $[1,1]$ 仅包含一个容器，初始即满足条件，故最早时刻为 0。

样例2

输入

5 4 5
2
4
1
3
1 5
2 4
1 3
4 5
3 3

输出

4
4
3
2
0

说明

初始独立族群：1、2、3、4、5。

• 第 1 次实验 $p=2$：合并 2 和 3，族群 $\{2,3\}$，时刻 1。
• 第 2 次实验 $p=4$：合并 4 和 5，族群 $\{4,5\}$，时刻 2。
• 第 3 次实验 $p=1$：合并 1 与族群 $\{2,3\}$，得到 $\{1,2,3\}$，时刻 3。
• 第 4 次实验 $p=3$：合并族群 $\{1,2,3\}$ 与 $\{4,5\}$，全部连通，时刻 4。

查询 $[1,5]$：所有容器在时刻 4 首次全部连通，输出 4。 查询 $[2,4]$：容器 2 与 4 在时刻 4 首次成为同一族群，输出 4。 查询 $[1,3]$：时刻 3 首次连通，输出 3。 查询 $[4,5]$：时刻 2 首次连通，输出 2。 查询 $[3,3]$：单个容器，初始已满足，输出 0。

样例3

输入

4 2 4
1
3
1 4
1 2
2 3
3 3

输出

-1
1
-1
0

说明

容器 1、2、3、4。

• 第 1 次实验 $p=1$：合并 1 和 2，得到族群 $\{1,2\}$，时刻 1。
• 第 2 次实验 $p=3$：合并 3 和 4，得到族群 $\{3,4\}$，时刻 2。 两次实验后，两个族群之间从未合并。

询问 $[1,4]$：1 与 4 始终不在同一族群，输出 -1。 询问 $[1,2]$：在时刻 1 合并，输出 1。 询问 $[2,3]$：2 在族群 $\{1,2\}$，3 在族群 $\{3,4\}$，从未合并，输出 -1。 询问 $[3,3]$：单个容器，输出 0。