题目描述

S 市地铁一号线共有 $n$ 个车站，这些车站按由起点站到终点站的顺序分别编号为 $1\sim n$。

S 市地铁的计费规则如下：

• 一个收费区是一段包含若干连续车站的子段，整条线路被不重不漏地划分成了若干收费区，即，所有车站都在恰好一个收费区内。
• 在同一车站进站和出站，收费 $1$ 元。
• 乘车起点和终点是同一收费区内不同车站的，收费 $2$ 元。
• 否则，若乘车起点和终点之间包含了 $m$ 个完整收费区，则收费 $2+m$ 元。具体地，设车程的两个端点车站分别为 $a,b~(a<b)$，则满足 $a\le l_x \le r_x \le b$ 的收费区 $x$ 的数量即为 $m$，其中 $l_x,r_x$ 是收费区 $x$ 的左右端点。

收费区如下定义：

• 给出 $k + 1$ 个分界点 $1=p_0 < p_1<p_2<\ldots<p_k=n+1$，则第 $i$ 个收费区包含所有满足 $p_{i-1}\le x<p_i$ 的车站 $x$。即收费区 $i$ 的左右端点分别为 $l_i=p_{i-1}$ 和 $r_i=p_i-1$。

你需要回答 $q$ 次询问，每次询问从车站 $i$ 到车站 $j$ 的收费。

输入格式

第一行两个由空格分隔的正整数 $n,k$。

第二行 $k+1$ 个由空格分隔的正整数，表示分界点。第 $i$ 个输入的正整数表示 $p_{i-1}$。

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

接下来 $q$ 行，每行输入两个正整数 $i,j$，表示一次询问。

输出格式

对于每组询问，输出一行一个整数表示答案。

10 4
1 3 5 7 11
6
2 2
1 3
1 4
10 1
6 9
3 4

1
3
4
6
2
2

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

1
5
6

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

3
2
1
4
2

提示

样例 1 解释

按照题目中的定义，我们将线路中的 $10$ 个车站划分为 $k=4$ 个收费区：

• 收费区 $1$：包含车站 $1,2$。
• 收费区 $2$：包含车站 $3,4$。
• 收费区 $3$：包含车站 $5,6$。
• 收费区 $4$：包含车站 $7,8,9,10$。

考虑各个询问：

询问编号	出发站	到达站	车费	解释
$1$	$2$		$1$ 元	同站进出，收费 $1$ 元
$2$	$1$	$3$	$3$ 元	$1,3$ 两站之间包含收费区 $1$ 中所有车站，收费 $2+1=3$ 元
$3$		$4$	$4$ 元	$1,4$ 两站之间包含收费区 $1,2$ 中所有车站，收费 $2+2=4$ 元
$4$	$10$	$1$	$6$ 元	$1,10$ 两站之间包含收费区 $1,2,3,4$ 中所有车站，收费 $2+4=6$ 元
$5$	$6$	$9$	$2$ 元	$6,9$ 两站之间没有包含任何一个收费区中所有的车站，收费 $2+0=2$ 元
$6$	$3$	$4$		$3,4$ 两站均属收费区 $2$，收费 $2$ 元

样例 2 解释

此样例满足 $k=n$ 的限制。

样例 3 解释

此样例满足 $k=2$ 的限制。

数据范围与约定

对于全部数据，满足 $1\le k\le 1000, 1\le n\le 10^9,k\le n,1\le q\le10^5$。各测试点的详细数据范围见下表。

测试点	$n$	$q$	特殊性质
$1\sim 2$	$\le 1000$	$\le 1000$	A
$3\sim 4$			B
$5\sim 7$			无
$8\sim 10$		$\le 10^5$
$11\sim 13$	$\le 10^5$	$\le 1000$
$14\sim 15$	$\le 10^9$	$\le 10^5$	C
$16\sim 20$			无

特殊性质 A：保证 $k=n$。

特殊性质 B：保证 $k=2$。

特殊性质 C：保证 $n$ 是 $k$ 的倍数且所有收费区大小相等。