Arithmetic

时间限制： 2s
空间限制： 512M

Description

对于一个整数序列 $A$，你可以进行两种操作：

• 在序列任意位置插入一个任意值的元素，花费为 1；
• 交换序列中任意两个元素的值，花费为 0。

对于给定的常数 $d$，定义 $f(A)$ 为将 $A$ 变为一个公差为 $d$ 的等差数列所需的最小花费。特别地，若无论怎样操作都无法变为一个公差为 $d$ 的等差序列，定义 $f(A) = 0$。

现在给出一个长为 $n$ 的序列 $S$，$q$ 次询问，每次给出 $l, r$，你需要回答：

其中 $S[i \dots j]$ 表示 $S$ 的第 $i$ 个元素到第 $j$ 个元素构成的子串（从 1 开始标号）。

Input

第一行三个整数 $n, d, q$。

第二行 $n$ 个整数，表示 $S$ 序列。

接下来 $q$ 行，每行两个整数 $l, r$，表示一组询问。

Output

输出 $q$ 行，每行一个整数表示询问答案。

Sample

Input

6 2 3
6 4 2 8 8 1
1 2
2 4
1 6

Output

0
3
3

Explanation

$f(\{2, 8\}) = 2, f(\{4, 2, 8\}) = 1$，其余子串的 $f()$ 均为 0。

Subtasks

对所有数据，保证 $0 \leq n, q \leq 3 \times 10^5, 0 \leq S_i \leq 10^7, 1 \leq d \leq 10^7$。

• Subtask1(3%)：$n = q = 0$；
• Subtask2(16%)：$n, q \leq 50$；
• Subtask3(16%)：$n \leq 5000$；
• Subtask4(19%)：$q = d = l = 1, r = n$，$S$ 是一个随机生成的 $1 - n$ 的排列；
• Subtask5(24%)：$q = l = 1, r = n$；
• Subtask6(22%)：没有特殊的限制。