数轴移动

题目描述

在一条线上给定 $n$ 个点，其中第 $i$ 个点的位置是 $a_i$。

当你在某一个点上时，你可以花费 $1$ 的代价走到离当前点最近的那个点，或是走到其他的点，并花费那个点与当前点的距离 $|a_i-a_j|$ 的代价。

给定 $m$ 组询问，对于每组询问，给定 $x$ 和 $y$，求从第 $x$ 个点移动到第 $y$ 个点的最小代价。

共有多组测试数据，所有测试点的 $n$ 的总和不超过 $2\times 10^5$，所有测试点的 $m$ 的总和不超过 $2 \times 10^5$，对于任意的 $a_i$，都有 $0\le a_i\le10^9$，任意一个点与左边一个点的距离都不等于该点与右边一个点的距离。

输入格式

第一行包含一个整数 $T(T\leq 10^4)$，表示测试数据的组数，第二行包含一个整数 $n(n \leq 2 \times 10^5)$，表示坐标轴上的点数，接下来一行包含 $n$ 个整数 $a_i$，表示第 $i$ 个点在坐标轴上的位置，且保证 $a_i \leq 10^9$ 且 $a_i < a_{i + 1}$，然后再下一行包含一个整数 $m(m\leq 2 \times 10^5)$，表示询问个数;接下来 $m$ 行，每行包含两个整数 $x;y(1 \le x \le y \le n)$，表示询问的点。

输出格式

对于每个询问，输出一个整数，表示最小移动到代价。

样例 #1

样例输入 #1

1
5
0 8 12 15 20
5
1 4
1 5
3 4
3 2
5 1

样例输出 #1

3
8
1
4
14