Description

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

最初，此网格中的所有单元格都被涂成 白色，除了最右侧的一列单元格，它们全部被涂成 黑色。

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

一些机器人将被放置在最左侧的一列单元格中，并根据它们所在单元格的颜色进行移动：

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

机器人不会相互碰撞，每个机器人独立移动。多个机器人可以占据同一个单元格。

一次查询由两个整数 $a$ 和 $b$ 组成（$1 \leq a < b \leq h$）。对于每个 $a \leq c \leq b$，都会有一个机器人从 $(c, 0)$ 位置开始。在所有可能的特殊单元格红色或蓝色涂色方案中，确定机器人最终可能占据的不同单元格的最小数量。

请注意，不同的查询可能会导致不同的特殊单元格涂色方案。

Input Format

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

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

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

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

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

Output Format

你的程序必须将输出写入标准输出。

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

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

2
1
1

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
3
2
2
3
1
1
3
1
3
2
1
1
3
3
4
1
2
1

Hint

子任务

对于所有测试用例，输入满足以下约束条件：

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

你的程序将在满足以下特殊性质的输入数据上进行测试：

样例 1 解释

此样例适用于子任务 $1, 4, 5$。

网格的颜色如下，特殊单元格用紫色表示。

对于第一个查询，我们可以将 $(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 解释

此样例适用于子任务 $1, 4, 5$。