Đề bài

Robert đang tham dự CEOI 2024. Cậu gần như đã hoàn thành lời giải cho bài khó nhất trong ngày, và còn tin chắc lời giải sẽ đạt \(100\) điểm! Chỉ còn một vấn đề nhỏ: cậu đã gõ sai một chỗ. Tệ hơn nữa, con chuột máy tính yêu thích mà cậu dùng từ năm 2008 dường như cuối cùng cũng đã hỏng và hoàn toàn không phản hồi. Vì vậy, cậu phải dùng các phím mũi tên trên bàn phím để di chuyển đến chỗ gõ sai.

Chương trình của Robert có \(N\) dòng với độ dài lần lượt là \(l_1,l_2,\ldots,l_N\). Robert luôn kết thúc chương trình bằng một dòng rỗng, do đó \(l_N=0\).

Con trỏ có thể nằm giữa hai ký tự, ở đầu dòng hoặc ở cuối dòng. Vì vậy, dòng \(i\) có \(l_i+1\) vị trí con trỏ, gọi là các cột, được đánh số từ \(1\) đến \(l_i+1\). Ví dụ, con trỏ ở dòng \(2\), cột \(6\) trông như sau:

![Con trỏ ở vị trí (2, 6)https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_2d60f30a.svg

Robert muốn di chuyển con trỏ từ dòng \(s_l\), cột \(s_c\) đến dòng \(e_l\), cột \(e_c\). Cậu muốn biết số lần nhấn phím ít nhất cần thiết.

Hai phím mũi tên ngang hoạt động khá đơn giản. Nhấn phím trái sẽ đưa con trỏ sang cột trước đó, trừ khi con trỏ đang ở đầu một dòng; khi ấy, con trỏ sẽ chuyển đến cuối dòng trước. Tương tự, nhấn phím phải sẽ đưa con trỏ sang cột tiếp theo, hoặc đến đầu dòng kế tiếp nếu con trỏ đang ở cuối dòng.

Ví dụ, hai lần nhấn phím trái có thể diễn ra như sau:

![Con trỏ di chuyển sau hai lần nhấn phím tráihttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_8cd5e304.svg

Và hai lần nhấn phím phải có thể diễn ra như sau:

![Con trỏ di chuyển sau hai lần nhấn phím phảihttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_176db26f.svg

Nhấn phím trái tại vị trí đầu tiên của tệp hoặc nhấn phím phải tại vị trí cuối cùng của tệp sẽ không có tác dụng.

Hai phím mũi tên dọc phức tạp hơn một chút. Nhấn phím lên sẽ đưa con trỏ đến dòng trước và nhấn phím xuống sẽ đưa con trỏ đến dòng sau mà không thay đổi số cột. Tuy nhiên, nếu cột đó nằm quá cuối dòng mới, con trỏ sẽ chuyển đến cuối dòng ấy.

Ví dụ, các lần nhấn phím lên có thể diễn ra như sau:

![Con trỏ di chuyển sau hai lần nhấn phím lênhttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_87944286.svg

Và các lần nhấn phím xuống có thể diễn ra như sau:

![Con trỏ di chuyển sau hai lần nhấn phím xuốnghttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_707401b0.svg

Nếu nhấn phím lên hoặc xuống khiến con trỏ phải chuyển đến một dòng không tồn tại, con trỏ sẽ không di chuyển.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), là số dòng trong chương trình của Robert.

Dòng thứ hai chứa hai số nguyên \(s_l\) và \(s_c\), cách nhau bởi dấu cách, là vị trí ban đầu của con trỏ.

Dòng thứ ba chứa hai số nguyên \(e_l\) và \(e_c\), là vị trí đích của con trỏ.

Dòng thứ tư chứa \(N\) số nguyên \(l_1,l_2,\ldots,l_N\), cách nhau bởi dấu cách, là độ dài của từng dòng.

Dữ liệu ra

In một dòng chứa một số nguyên, là số lần nhấn phím ít nhất để di chuyển con trỏ từ \((s_l,s_c)\) đến \((e_l,e_c)\).

Giới hạn

• \(1\le N\le 10^6\).
• \(0\le l_i\le 10^9\) với mọi \(1\le i\le N\).
• \(l_N=0\).
• \(1\le s_l,e_l\le N\).
• \(1\le s_c\le l_{s_l}+1\).
• \(1\le e_c\le l_{e_l}+1\).

Chấm điểm

• Subtask 1 (5 điểm): \(N\le 2\).
• Subtask 2 (14 điểm): \(N\le 1\,000\) và \(l_i\le 5\,000\) với mọi \(1\le i\le N\).
• Subtask 3 (26 điểm): \(N\le 1\,000\).
• Subtask 4 (11 điểm): \(l_i=l_j\) với mọi \(1\le i,j\le N-1\).
• Subtask 5 (44 điểm): Không có ràng buộc bổ sung.

Ví dụ

5
3 1
2 8
7 10 9 9 0

3

5
1 20
3 25
25 10 40 35 0

16