Funnyland 被建模为一个大小为 $(h + 2) \times (w + 2)$ 的网格。网格的行从上到下编号为 $0$ 到 $h + 1$，列从左到右编号为 $0$ 到 $w + 1$。我们将位于第 $r$ 行第 $c$ 列的单元格称为单元格 $(r, c)$。

最初，网格中的所有单元格均为白色，最右侧一列除外，该列的所有单元格均为黑色。

第 $1$ 到 $w$ 列中每一列都恰好包含一个特殊单元格。这些特殊单元格中的每一个都要被涂成红色或蓝色。网格的边缘（即最顶行、最底行、最左列和最右列）永远不会包含特殊单元格。

若干机器人将被放置在最左列的单元格上，并根据其所在单元格的颜色移动：

• 如果单元格是白色的，机器人向右移动。
• 如果单元格是红色的，机器人向上移动。
• 如果单元格是蓝色的，机器人向下移动。
• 如果单元格是黑色的，机器人不移动。

机器人之间不会发生碰撞；每个机器人独立于其他机器人移动。允许多个机器人占据同一个单元格。

一个询问包含两个整数 $a$ 和 $b$ ($1 \le a < b \le h$)。对于每个 $a \le c \le b$，都有一个机器人从 $(c, 0)$ 出发。在所有可能的特殊单元格涂色方案（红色或蓝色）中，确定机器人最终能够占据的互不相同的单元格数量的最小值。

注意，不同的询问可能导致特殊单元格被涂成不同的颜色配置。

输入格式

程序必须从标准输入读取数据。

第一行包含两个空格分隔的整数 $h$ 和 $w$。

第二行包含 $w$ 个空格分隔的整数 $x[1], x[2], \dots, x[w]$，表示特殊单元格位于 $(x[1], 1), (x[2], 2), \dots, (x[w], w)$。

第三行包含一个整数 $q$。

接下来的 $q$ 行，每行包含两个空格分隔的整数。第 $i$ 行包含 $a[i]$ 和 $b[i]$。

输出格式

程序必须输出到标准输出。

输出应包含 $q$ 行。第 $i$ 行应包含一个整数，即第 $i$ 个询问的答案。

子任务

对于所有测试用例，输入满足以下范围：

• $1 \le w, q \le 200\,000$
• $2 \le h \le 200\,000$
• $1 \le x[j] \le h$，对于所有 $1 \le j \le w$
• $1 \le a[i] < b[i] \le h$，对于所有 $1 \le i \le q$

程序将在满足以下限制的输入实例上进行测试：

样例

样例输入 1

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

样例输出 1

2
1
1

说明 1

网格颜色配置如下，特殊单元格以紫色标出：

对于第一个询问，我们可以将位于 $(3, 1)$ 和 $(4, 3)$ 的特殊单元格涂成蓝色，将 $(2, 2)$ 和 $(1, 4)$ 涂成红色，以达到以下效果：

• 从 $(1, 0)$ 出发的机器人移动到 $(1, 1), (1, 2), (1, 3), (1, 4), (0, 4), (0, 5)$，最终停在 $(0, 5)$。
• 从 $(2, 0)$ 出发的机器人移动到 $(2, 1), (2, 2), (1, 2), (1, 3), (1, 4), (0, 4), (0, 5)$，最终停在 $(0, 5)$。
• 从 $(3, 0)$ 出发的机器人移动到 $(3, 1), (4, 1), (4, 2), (4, 3), (5, 3), (5, 4)$，最终停在 $(5, 5)$。
• 从 $(4, 0)$ 出发的机器人移动到 $(4, 1), (4, 2), (4, 3), (5, 3), (5, 4)$，最终停在 $(5, 5)$。

机器人最终停在 $2$ 个不同的单元格 $(0, 5)$ 和 $(5, 5)$ 上，因此正确输出为 $2$。

对于第二个询问，我们可以将特殊单元格涂色如下：

从 $(1, 0), (2, 0)$ 和 $(3, 0)$ 出发的机器人最终都停在 $(0, 5)$。

对于第三个询问，我们可以将特殊单元格涂色如下：

从 $(2, 0), (3, 0)$ 和 $(4, 0)$ 出发的机器人最终都停在 $(3, 5)$。

样例输入 2

15 16
5 15 3 4 13 8 3 7 14 6 2 10 11 12 9 1
20
4 10
7 15
5 15
2 6
7 15
5 15
12 15
13 14
5 14
13 14
2 11
3 11
2 5
9 11
3 15
5 14
1 13
3 7
7 12
4 8

样例输出 2

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