← 返回题目列表

Codeforces · 477/E

E. Dreamoon 和记事本

中文机器翻译题面 查看原题

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、向下。