题目描述
小 L 喜欢爬山，但是小 L 不喜欢正常的爬山，他喜欢用喷气背包爬山。
如果小L当前在 $(x,y)$，他可以花费 4 的代价到达 $(x-1,y+ 1)$，$(x,y+ 1)$，$(x+1,y+1)$，或花费 2 的代价到达 $(x-1,y)$，$(x+1,y)$，或花费 1 的代价到达 $(x-1,y-1)$，$(x,y- 1)$，$(x+1,y-1)$。
山可以用一个高度序列 ${h_n}$ 表示，由于被山阻挡，小 L 不能到达 $(x,y)$，其中 $y < h$。
小 L 有若干个询问，每个询问形如如果要从 $(i,h_i)$ 到达 $(j,h_j)$，最少需要多少代价。
输入格式
第一行两个整数 $n, m$ 表示山的长度和询问次数。
第二行 $n$ 个整数 $h_i$ 表示山的高度序列。
接下来 $m$ 行每行两个整数 $a,b$ 表示询问的起点和终点。
输出格式
$m$ 行，每行一个整数表示最小代价。
样例输入1
4 2
9 1 8 2
1 3
4 2样例输出1
3
31样例解释1
第一问走法是：右下，右。 第二问走法是：上 $\times 6$，右上，右下，下 $\times 6$。
样例输入输出2
见下发文件。
样例输入输出3
见下发文件。
数据规模
共 10 个测试点。
测试点 1,2 满足 $n,m,h_i \leq 50$。
测试点 3,4 满足 $n,m \leq 1000, h_i \leq 10^9$。
测试点 5,6,7 满足 $h_i$ 在 $[1, 10^9]$ 内随机，$a,b$ 在 $[1, n]$ 内随机。
对于所有数据，满足 $1 \leq n,m \leq 2 \times 10^5,1 \leq h_i \leq 10^9$。