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

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
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.