题目描述

题目译自 European Girls' Olympiad in Informatics 2024 Day2 T1. Circle Passing

今天是安努克进入高中的第一天，为了热身，她的体育老师组织全班玩一个认识名字的游戏。班级有 $2N$ 名学生，大多数互不认识，但有 $M$ 对形影不离的闺蜜。每名学生最多有一位闺蜜。

老师将所有学生安排成一个圆圈，依次编号为 $0$ 到 $2N - 1$。具体来说，对于每个 $0 \leq i < 2N - 1$，学生 $i$ 和 $i + 1$ 站在一起；此外，学生 $0$ 和 $2N - 1$ 也站在一起。

为了让大家结识新朋友，老师要求闺蜜站在圆圈的对面，尽可能远离彼此。即第 $i$ 对闺蜜分别站在位置 $k_i$ 和 $k_i + N$，其中 $0 \leq k_i < N$。

老师选择两名学生 $x$ 和 $y$，将球交给学生 $x$。你的目标是将球传到学生 $y$，但学生只能将球传给已经知道名字的同学。当然，闺蜜彼此知道名字；在游戏规则讲解时，每名学生还认识了站在身旁的两位同学的名字。除此之外，没有人知道其他同学的名字。

游戏共玩 $Q$ 次，每次老师都会选出两名学生。由于学生们不专心，他们在游戏中不会学习新名字。你的任务是计算每次游戏中从学生 $x$ 到学生 $y$ 的最少传球次数。

输入格式

第一行包含三个整数 $N, M, Q$，分别表示安努克班级学生总数 $2N$、闺蜜对数 $M$ 和游戏次数 $Q$。

第二行包含 $M$ 个整数 $k_0, \ldots, k_{M-1}$，其中 $k_i$ 描述第 $i$ 对闺蜜的位置。每对闺蜜分别站在位置 $k_i$ 和 $k_i + N$。每名学生最多有一位闺蜜。

接下来的 $Q$ 行每行包含两个整数 $x_i, y_i$，表示第 $i$ 次游戏中选出的两名学生。

输出格式

输出 $Q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次游戏所需的最少传球次数。

4 1 5
1
1 4
1 5
1 7
1 2
1 6

2
1
2
1
2

以下两幅图展示了第一个和第四个样例的安排。如果两名学生知道彼此的名字，他们之间有一条边连接。

在第一个样例的第一次游戏中，球交给学生 $1$。学生 $1$ 将球传给自己的闺蜜学生 $5$。学生 $5$ 再将球传给学生 $4$，总共需要两次传球。

6 1 3
5
5 7
5 1
5 11

2
3
1

4 2 4
2 3
0 2
0 3
0 6
0 7

2
2
2
1

5 2 5
0 4
0 9
1 8
8 3
1 6
3 9

1
3
3
3
2

500000000 4 3
543234 1234566 2300001 249999999
2334445 123567
6578996 12455726
3 269979899

2210878
5876730
231106567

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 5 \cdot 10^8$
• $1 \leq M \leq 5 \cdot 10^5$ 且 $M \leq N$
• $1 \leq Q \leq 2 \cdot 10^4$
• $0 \leq k_0 < k_1 < \ldots < k_{M-1} < N$
• $0 \leq x_i, y_i < 2N$ 且 $x_i \neq y_i$

详细子任务附加限制及分值如下表所示。