Dreamoon 刚刚使用 notepad.exe 创建了一个难题文档。该文档由n行文本组成,ai表示第i行的长度。他现在想知道移动光标的最快方法是什么,因为文档非常长。
令(r, c) 为当前光标位置,其中r 为行号,c 为光标在该行中的位置。我们有 1 ≤ r ≤ n 且 0 ≤ c ≤ ar。
假设当前光标位置在(r, c),我们可以在notepad.exe中使用以下六个操作来移动光标:
1. 上键:新光标位置 (nr, nc) = (max(r - 1, 1), min(anr, c))
2. 下键:新光标位置 (nr, nc) = (min(r + 1, n), min(anr, c))
3. 左键:新光标位置 (nr, nc) = (r, max(0, c - 1))
4.右键:新光标位置(nr, nc) = (r, min(anr, c + 1))
5. HOME键:新光标位置(nr, nc) = (r, 0)
6. END键:新光标位置(nr, nc) = (r, ar)
您将获得来自 Dreamoon 的文档描述(n 和序列 ai)和 q 查询。每个查询都会询问将光标从 (r1, c1) 移动到 (r2, c2) 所需的最少按键次数。
输入
第一行包含一个整数 n(1 ≤ n ≤ 400, 000) — 文本行数。
第二行包含 n 个整数 a1, a2, ..., an(1 ≤ ai ≤ 108)。
第三行包含一个整数 q(1 ≤ q ≤ 400, 000)。
接下来的 q 行包含四个整数 r1、c1、r2、c2,表示一个查询(1 ≤ r1、r2 ≤ n、0 ≤ c1 ≤ ar1、0 ≤ c2 ≤ ar2)。
输出
对于每个查询,打印查询结果。
示例
输入 #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
注意
在第一个示例中,第一个查询可以使用键来解决:HOME,对。
第二个查询可以通过按键解决:向下,向下,向下,END,向下。
第三个查询可以用以下键解决:down、END、down。
第四个查询可以通过按键解决:END、向下。