텍스트 편집기

Robert는 CEOI 2024에 참가하고 있다. 그날 가장 어려운 문제의 풀이를 거의 마쳤고, 100점을 받을 것이라고 확신한다. 다만 작은 오타가 하나 있다. 2008년부터 써 온 마우스가 마침내 고장 나서 전혀 반응하지 않는다. 그래서 키보드의 방향키만으로 오타 위치까지 커서를 옮겨야 한다.

Robert의 프로그램은 길이가 $l_1, l_2, \ldots, l_N$인 $N$개의 줄로 이루어져 있다. Robert는 항상 빈 줄로 프로그램을 끝내므로 $l_N = 0$이다. 커서는 두 문자 사이, 줄의 시작, 줄의 끝에 놓일 수 있다. 따라서 $i$번째 줄에는 $l_i + 1$개의 커서 위치(열)가 있으며, 1번부터 $l_i + 1$번까지 번호가 붙는다. 예를 들어 2번째 줄의 6번 열에 놓인 커서는 그 줄의 다섯 번째 문자 뒤에 있다.

Robert는 커서를 $s_l$번째 줄 $s_c$번 열에서 $e_l$번째 줄 $e_c$번 열로 옮기려 한다. 이때 필요한 키 입력 횟수의 최솟값을 구하라.

좌우 방향키는 단순하다. 왼쪽 키는 커서를 이전 열로 옮긴다. 다만 커서가 줄의 시작에 있으면 이전 줄의 끝으로 옮긴다. 오른쪽 키는 커서를 다음 열로 옮긴다. 다만 커서가 줄의 끝에 있으면 다음 줄의 시작으로 옮긴다. 파일의 맨 처음에서 왼쪽 키를 누르거나 파일의 맨 끝에서 오른쪽 키를 누르면 아무 효과가 없다.

상하 방향키는 조금 더 복잡하다. 위쪽 키는 커서를 이전 줄로, 아래쪽 키는 다음 줄로 옮기며, 열 번호는 바뀌지 않는다. 다만 새 줄의 길이를 넘어서게 되면 커서는 그 줄의 끝으로 옮겨간다. 위쪽 또는 아래쪽 키로 존재하지 않는 줄에 가려고 하면 커서는 움직이지 않는다.

첫 번째 줄에 Robert 풀이의 줄 수 정수 $N$이 주어진다.

두 번째 줄에는 초기 커서 위치를 나타내는 정수 $s_l$과 $s_c$가 주어진다.

세 번째 줄에는 목표 커서 위치를 나타내는 정수 $e_l$과 $e_c$가 주어진다.

네 번째 줄에는 각 줄의 길이를 나타내는 정수 $l_1, l_2, \ldots, l_N$이 공백으로 구분되어 주어진다.

커서를 $(s_l, s_c)$에서 $(e_l, e_c)$로 옮기는 데 필요한 키 입력 횟수의 최솟값을 한 줄에 정수 하나로 출력한다.

$1 \leq N \leq 10^6$

$1 \leq i \leq N$인 각 $i$에 대해 $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$