Dreamoon and Notepad

题面翻译

你有一个 $n$ 行的文本，从上往下第 $i$ 行文本的长度是 $a_i$。同时，文本还有一个光标，其位置记作 $(r,c)$，表示其在第 $r$ 行文本的第 $c$ 个字符的后面（假如 $c=0$ 则其在第 $r$ 行的开头）。

你可以操作如下按键来控制一个位置在 $(r,c)$ 的光标移动到位置 $(r',c')$：

• up：$(r',c')=\Big(r-1,\min\{a_{r'},c\}\Big)$

• down：$(r',c')=\Big(r+1,\min\{a_{r'},c\}\Big)$

• left：$(r',c')=\Big(r,\max\{0,c-1\}\Big)$

• right：$(r',c')=\Big(r,\min\{a_{r},c+1\}\Big)$

• HOME：$(r',c')=\Big(r,0\Big)$

• END：$(r',c')=\Big(r,a_r\Big)$

下面，给出 $q$ 个询问 $(r_1,c_1),(r_2,c_2)$，询问如果光标在位置 $(r_1,c_1)$，要想移动到 $(r_2,c_2)$ 最少需要按多少次按键。

• $n,q\leq4\times10^5,1\leq a_i\leq10^8$

题目描述

Dreamoon has just created a document of hard problems using notepad.exe. The document consists of $n$ lines of text, $a_{i}$ denotes the length of the $i$ -th line. He now wants to know what is the fastest way to move the cursor around because the document is really long.

Let $(r,c)$ be a current cursor position, where $r$ is row number and $c$ is position of cursor in the row. We have $1<=r<=n$ and $0<=c<=a_{r}$ .

We can use following six operations in notepad.exe to move our cursor assuming the current cursor position is at $(r,c)$ :

1. up key: the new cursor position $(nr,nc)=(max(r-1,1),min(a_{nr},c))$
2. down key: the new cursor position $(nr,nc)=(min(r+1,n),min(a_{nr},c))$
3. left key: the new cursor position $(nr,nc)=(r,max(0,c-1))$
4. right key: the new cursor position $(nr,nc)=(r,min(a_{nr},c+1))$
5. HOME key: the new cursor position $(nr,nc)=(r,0)$
6. END key: the new cursor position $(nr,nc)=(r,a_{r})$

You're given the document description ( $n$ and sequence $a_{i}$ ) and $q$ queries from Dreamoon. Each query asks what minimal number of key presses is needed to move the cursor from $(r_{1},c_{1})$ to $(r_{2},c_{2})$ .

输入格式

Dreamoon has just created a document of hard problems using notepad.exe. The document consists of $n$ lines of text, $a_{i}$ denotes the length of the $i$ -th line. He now wants to know what is the fastest way to move the cursor around because the document is really long.

Let $(r,c)$ be a current cursor position, where $r$ is row number and $c$ is position of cursor in the row. We have $1<=r<=n$ and $0<=c<=a_{r}$ .

We can use following six operations in notepad.exe to move our cursor assuming the current cursor position is at $(r,c)$ :

1. up key: the new cursor position $(nr,nc)=(max(r-1,1),min(a_{nr},c))$
2. down key: the new cursor position $(nr,nc)=(min(r+1,n),min(a_{nr},c))$
3. left key: the new cursor position $(nr,nc)=(r,max(0,c-1))$
4. right key: the new cursor position $(nr,nc)=(r,min(a_{nr},c+1))$
5. HOME key: the new cursor position $(nr,nc)=(r,0)$
6. END key: the new cursor position $(nr,nc)=(r,a_{r})$

You're given the document description ( $n$ and sequence $a_{i}$ ) and $q$ queries from Dreamoon. Each query asks what minimal number of key presses is needed to move the cursor from $(r_{1},c_{1})$ to $(r_{2},c_{2})$ .

输出格式

For each query print the result of the query.

样例 #1

样例输入 #1

9
1 3 5 3 1 3 5 3 1
4
3 5 3 1
3 3 7 3
1 0 3 3
6 0 7 3

样例输出 #1

2
5
3
2

样例 #2

样例输入 #2

2
10 5
1
1 0 1 5

样例输出 #2

3

提示

In the first sample, the first query can be solved with keys: HOME, right.

The second query can be solved with keys: down, down, down, END, down.

The third query can be solved with keys: down, END, down.

The fourth query can be solved with keys: END, down.