解题思路

核心思路

观察操作的本质：第 $k$ 秒选择位置 $x$ 时，若 $x$ 与 $x+1$ 颜色不同，则将 $x$ 所在的整个同色区间染成 $x+1$ 的颜色。这等价于将 $x$ 所在连通块与 $x+1$ 所在连通合并，合并时间为 $k$。

这提示我们使用 Kruskal 重构树 来维护连通块的合并过程：

1. 构建重构树：初始时每个位置 $i$（$1\le i\le n$）为独立的叶子节点。遍历 $t$ 次操作，第 $k$ 次操作选择位置 $x$ 时：

题目内容

有一排 $n$ 个位置，从左到右编号为 $1,2,…,n$。每个位置都有一个 “颜色编号”（就是一个整数）。

一开始（记作第 $0$ 秒），第 $i$ 个位置的颜色为 $i$。

接下来会发生 $t$ 次操作，按顺序依次执行。第 $k$ 次操作（也就是第 $k$ 秒）给出一个位置 $x$ (保证 $1≤x≤n−1$)，并进行如下事情：

• 先找到一个最大区间 $[L,R]$，满足：

  • $L≤x≤R$；
  • 在第 $k−1$ 秒结束后，区间 $[L,R]$ 内所有位置的颜色都与位置 $x$ 的颜色相同；
  • $[L,R]$ 不能再向左或向右扩展（也就是 $L−1$ 或 $R+1$ 的颜色与位置 $x$ 不同，或者越界）。

• 然后，把区间 $[L,R]$ 内所有位置的颜色，都改成 “位置 $x+1$ 在第 $k−1$ 秒结束后的颜色”。

现在有 $q$ 次询问。每次询问给出一个区间 $[l,r]$，你需要回答：最早在第几秒（允许是第 $0$ 秒），区间 $[l,r]$ 内只存在一种颜色（也就是 $l,l+1,…,r$ 这些位置的颜色全部相同）。如果直到第 $t$ 秒都做完了也没发生，输出 $−1$。

输入描述

在一行上输入三个整数 $n,t,q (2≤n,t,q≤2×10^5)$，表示位置数量、操作次数、询问次数。

此后 $t$ 行，每行输入一个整数 $x (1≤x≤n−1)$，表示这一秒选择的位置。

此后 $q$ 行，每行输入两个整数 $l,r (1≤l≤r≤n)$，表示一次询问的区间。

输出描述

对于每个询问，新起一行输出一个整数，表示最早在第几秒区间 $[l,r]$ 内只存在一种颜色。若不存在，输出 $−1$。

样例1

输入

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

输出

4
3
2
0
4

说明

第 $0$ 秒颜色为 {$1,2,3,4,5$}。

第 $1$ 秒选择 $x=4$，位置 $4$ 的颜色段只有它自己，染成位置 $5$ 的颜色后，颜色变为 {$1,2,3,5,5$}。

第 $2$ 秒选择 $x=3$，颜色变为 {$1,2,5,5,5$}。

第 $3$ 秒选择 $x=2$，颜色变为 {$1,5,5,5,5$}。

第 $4$ 秒选择 $x=1$，颜色变为 {$5,5,5,5,5$}。

因此：

• 区间 $[1,5]$ 最早在第 $4$ 秒变成一种颜色；

• 区间 $[2,5]$ 最早在第 $3$ 秒变成一种颜色；

• 区间 $[3,5]$ 最早在第 $2$ 秒变成一种颜色；

• 区间 $[1,1]$ 在第 $0$ 秒就已经只有一种颜色；

• 区间 $[1,2]$ 最早在第 $4$ 秒变成一种颜色。

样例2

输入

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

输出

-1
1
-1
0