You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

代码

Zky 正在参加 2024 年的 IOI。 他已经完成了当天最难问题的解决方案， 不仅如此，他非常确信它将获得 100 分！ 但有一个小问题：他打错了字！ 更糟糕的是，自 2008 年以来他一直使用的最喜欢的电脑鼠标似乎终于坏了，根本无法响应。 因此，他将不得不使用键盘上的箭头键来导航到打字错误的地方。

Zky 的程序有 $N$ 行，长度为 $l_1, l_2, \ldots, l_N$。 Zky 总是在程序末尾添加一个空行，因此 $l_N = 0$。

光标可以放置在两个字符之间，以及一行的开始或结束。

因此，第 $i$ 行有 $l_i + 1$ 个可能的光标位置（称为列） 编号从 $1$ 到 $l_i + 1$。 例如，以下是光标放置在第 2 行第 6 列的样子：

Zky 想要将光标从第 $s_l$ 行第 $s_c$ 列移动到第 $e_l$ 行第 $e_c$ 列。 他想知道完成此操作所需的最小按键次数。

水平箭头键很简单。 按下 ← 键将移动光标到前一列，除非光标在行的开始位置，在这种情况下，它将移动到前一行的结束位置。 同样，按下 → 键将移动光标到下一列， 或者如果光标在行的结束位置，则移动到下一行的开始位置。

例如，按下 ← 键可能如下所示：

按下 → 键可能如下所示：

在文件的最开始按下 ← 键，或在文件的最终按下 → 键将不会有任何效果。

垂直箭头键稍微复杂一些。 按下 ↑ 键将移动光标到前一行， 按下 ↓ 键将移动光标到下一行，且不改变列号。 然而，如果这会将光标放置在新行的末尾之外，光标将跳转到该行的末尾。

例如，按下 ↑ 键可能如下所示：

按下 ↓ 键可能如下所示：

如果按下 ↑ 或 ↓ 键会将光标放置在不存在的行上， 光标将不会移动。

输入

第一行输入包含整数 $N$，即 Zky 的代码的行数。

第二行包含两个整数 $s_l$ 和 $s_c$，由空格分隔，即初始光标位置。

类似地，第三行包含两个整数 $e_l$ 和 $e_c$，即目标光标位置。

第四行包含 $N$ 个由空格分隔的整数 $l_1, l_2,\ldots, l_N$，即每一行的长度。

输出

你的程序应该输出一行，包含一个整数，即从 $(s_l, s_c)$ 移动光标到 $(e_l, e_c)$ 所需的最小按键次数。

5
3 1
2 8
7 10 9 9 0

3

Zky 可以通过按下 ↑ ← →键，按此顺序使用三个按键将光标移动到目标位置：

或者，他可以通过按下 ← ↑ ↓ 键同样快地将光标移动到目标位置。 可以很容易地证明，使用最多两个按键无法达到目标位置。

5
1 20
3 25
25 10 40 35 0

16

最短的可能按键序列包括两次按下 ↓ 键，然后是十四次按下 → 键。

限制条件

• $1 \leq N \leq 10^6$
• $0 \leq l_i \leq 10^9$
• $l_N = 0$
• $1 \leq s_l, e_l \leq N$
• $1 \leq s_c \leq l_{s_l} + 1$
• $1 \leq e_c \leq l_{e_l} + 1$。

子任务

1. （5分）$N \leq 2$

2. （14分）$N \leq 1\,000$, $l_i \leq 5\,000$

3. （26分）$N \leq 1\,000$

4. （11分）$l_i = l_j$ ($1 \leq i, j \leq N - 1$）

5. （44分）没有额外的限制条件