题目描述

题目译自 CEOI 2024 Day1 T3「Text editor」

罗伯特正在参加 2024 年 CEOI 编程竞赛。他几乎完成了当天最难的一道题的代码，而且他确信能拿满分！但问题出在一个小小的细节上：他打错了一个字！更糟糕的是，他从 2008 年就开始使用的那只心爱鼠标彻底罢工了，一点反应也没有。因此，他只能用键盘上的方向键移动光标去找到那个错别字。

罗伯特的程序有 $N$ 行，每行的长度分别为 $l_1, l_2, \ldots , l_N$。罗伯特总是以空行作为程序的结尾，所以 $l_N = 0$。光标可以放在两个字符之间，也可以放在行的开头或结尾。因此，第 $i$ 行有 $l_i + 1$ 个可用的光标位置（称为列），编号从 $1$ 到 $l_i + 1$。例如，下面是光标位于第 $2$ 行第 $6$ 列的情况：

罗伯特想把光标从第 $s_l$ 行的第 $s_c$ 列移动到第 $e_l$ 行的第 $e_c$ 列。他想求出最少需要的按键次数。

水平方向键的使用比较简单。按下 左键 会将光标移动到前一列，除非光标位于行首，则会移动到前一行的行尾。类似地，按下 右键 会将光标移动到后一列，或者如果光标位于行尾，则会移动到下一行的行首。

例如，左键 的移动可以像这样：

而 右键 的移动可以像这样：

在文件的最开头按下 左键 或在文件的最结尾按下 右键 都不会有任何效果。

垂直方向键的使用稍微复杂一些。按下 上键 会将光标移动到上一行，按下 下键 会将光标移动到下一行，列数不会改变。但是，如果这样会使光标超出新行的结尾，光标则会跳到该行末尾。

例如，上键 的移动可以像这样：

而 下键 的移动可以像这样：

如果按下 上键 或 下键 会把光标移动到不存在的行，则光标根本不会移动。

输入格式

输入的第一行包含一个整数 $N$，表示罗伯特程序的行数。

第二行包含两个空格隔开的整数 $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

5
1 20
3 25
25 10 40 35 0

16

提示

样例解释 1

罗伯特可以通过按顺序按 上键、左键 和 下键三个键来将光标移动到目标位置：

或者，他也可以通过按 左键、上键 和 下键 来同样快速地将光标移动到目标位置。

样例解释 2

可以很容易地证明，不可能使用最多两个按键到达目标位置。

最短的可能按键序列是按两次 下键 然后按十四次 右键。

对于所有输入数据，满足：

• $1 \leq N \leq 10^6$
• $0 \leq l_i \leq 10^9\ (1\leq i\leq n)$
• $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$	$N \leq 2$	$5$
$2$	$N \leq 1\,000, l_i \leq 5\,000\ (1 \leq i \leq N)$	$14$
$3$	$N \leq 1\,000$	$26$
$4$	$l_i = l_j\ (1 \leq i, j \leq N - 1)$	$11$
$5$	无附加限制	$44$