CTH cần xây một bức tường từ các khối đá hình lập phương với kích thước ~1 \times 1 \times 1~. Bức tường gồm nhiều cột xếp cạnh nhau, mỗi cột được tạo thành bằng cách xếp chồng các khối đá. Các cột tạo thành bức tường có thể có độ cao khác nhau, độ cao của một cột là số khối đá tạo nên cột đó. CTH muốn xây một bức tường có đúng ~n~ cột đánh số lần lượt từ ~1~ tới ~n~, cột thứ ~i~ có độ cao ~a_i~.

CTH chế tạo một con robot xây tường, để robot hoạt động theo ý muốn cần truyền vào ~2~ dãy số có cùng độ dài ~H~ (~H~ là số nguyên không âm bất kỳ):

• Dãy ~L~: ~L_1, L_2, L_3, ..., L_H~
• Dãy ~R~: ~R_1, R_2, R_3, ..., R_H~
• ~1 \leq L_i \leq R_i \leq n~ với mọi ~1 \leq i \leq H~

Robot thực hiện ~H~ bước, tại bước thứ ~i~, robot thả các khối đá từ độ cao ~i~ xuống các cột có chỉ số thuộc đoạn ~[L_i, R_i]~. Tuy nhiên robot lại rất vụng về nên khối đá chỉ có thể xếp lên tường một cách hoàn hảo nếu như ngay dưới nó (tức ở độ cao ~i-1~) là mặt đất hoặc là một khối đá khác (coi độ cao của mặt đất là ~0~). Tất cả những trường hợp còn lại, khối đá sẽ rơi xuống và bị vỡ ngay lập tức.

Dễ thấy con robot khá phế vì có một số bức tường có dạng đặc biệt không thể nào chỉ dùng robot mà xây hoàn chỉnh được, vì vậy CTH có thể phải đi sửa chữa lại một tí để bức tường đúng ý mình. Cụ thể, với những cột đá cao hơn mong muốn, CTH sẽ phải leo lên lấy khối đá trên cùng của cột đó xuống, số bậc thang phải leo là ~2~ lần độ cao của cột trước khi lấy khối đá xuống. Còn với những cột đá thấp hơn mong muốn, anh phải ôm ~1~ khối đá leo lên để đặt nó lên trên, số bậc thang phải leo là ~2~ lần độ cao của cột sau khi đặt khối đá mới lên.

Cho thông tin về bức tường CTH muốn xây, hãy giúp CTH điều khiển con robot sao cho tổng số bậc thang phải leo để hoàn thành bức tường là ít nhất có thể.

Lưu ý: Sau khi robot hoàn thành ~H~ bước xây, CTH mới bắt đầu leo lên để chỉnh sửa theo ý muốn của mình.

Input

• Dòng đầu tiên cho số nguyên dương ~n~ ~(1 \leq n \leq 10^5)~
• Dòng thứ hai chứa dãy gồm ~n~ số nguyên không âm ~a_1, a_2, a_3, ..., a_n~ mô tả bức tường mong muốn của CTH ~(a_i \leq 10^6)~

Output

• In ra ~1~ số nguyên duy nhất là số bậc thang ít nhất cần phải leo để hoàn thành bức tường.

Sample Input 1

5
9 0 9 0 9

Sample Output 1

180

Sample Input 2

3
2 1 3

Sample Output 2

4

Note

Sample 1

CTH chọn:

• ~H = 9~
• ~L = \{1, 1, 1, 1, 1, 1, 1, 1, 1\}~
• ~R = \{5, 5, 5, 5, 5, 5, 5, 5, 5\}~

Sau khi robot hoàn thành, độ cao của các cột đều là ~9~.

Đối với cột thứ ~2~ và cột thứ ~4~, tại mỗi cột CTH mất ~18~ lần leo thang để lấy khối đá trên cùng xuống, ~16~ lần để lấy khối tiếp theo, ~14~ lần cho khối tiếp theo nữa,..., ~2~ lần cho khối đá dưới cùng. Tổng cộng là ~90~ lần leo cho mỗi cột.

Có thể chứng minh được đây là phương án tối ưu.

Sample 2

CTH chọn:

• ~H = 3~
• ~L = \{1, 3, 2\}~
• ~R = \{3, 3, 3\}~

Quy trình xây tường của Robot như sau:

• Sau bước thứ nhất, độ cao của các cột lần lượt là: ~{1, 1, 1}~.
• Sau bước thứ hai, độ cao của các cột lần lượt là: ~{1, 1, 2}~.
• Sau bước thứ ba, độ cao của các cột lần lượt là: ~{1, 1, 3}~. Lưu ý, tại bước này robot có thả ~1~ khối đá xuống cột thứ ~2~, nhưng vì trước đó cột ~2~ có độ cao là ~1~ mà khối đá lại được thả từ độ cao ~3~ nên nó đã rơi xuống và vỡ.

Sau khi robot thực hiện xong phần việc của nó, CTH cần đặt thêm ~1~ khối đá lên trên cột ~1~, số lần leo cần thiết là ~4~. Dễ thấy, không có phương án nào tối ưu hơn.

Subtask

• ~20\%~ số test có ~n, a_i \le 10^3~
• ~40\%~ số test tiếp theo có ~n \le 10^3~
• ~40\%~ số test còn lại không có điều kiện gì thêm