Cho dãy số nguyên không âm ~a~ = (~a_1,a_2, … , a_n~). Bạn được thực hiện các phép biến đổi, ở mỗi phép biến đổi bạn tùy chọn một dãy các phần tử liên tiếp trong dãy và trừ tất cả các phần tử này đi 1 đơn vị.

Yêu cầu: Dùng số phép biến đổi ít nhất để biến tất cả các phần tử trong dãy trở thành 0.

Input

Dòng 1 chứa số nguyên dương ~n ≤ 10^6~

Dòng 2 chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ cách nhau bởi dấu cách (~0 ≤ a_i ≤ 10^6~)

Output

Ghi ra một số nguyên duy nhất là số phép biến đổi cần thực hiện

Test mẫu

Input Sample Output

10
1 2 5 3 4 2 1 5 4 1

Output

10

Giải thích

~1 2 \textbf{5} 3 4 2 1 5 4 1~

~1 2 \textbf{4} 3 4 2 1 5 4 1~

~1 2 3 3 \textbf{4} 2 1 5 4 1~

~1 2 \textbf{3 3 3} 2 1 5 4 1~

~1 \textbf{2 2 2 2 2} 1 5 4 1~

~1 1 1 1 1 1 1 \textbf{5} 4 1~

~1 1 1 1 1 1 1 \textbf{4 4} 1~

~1 1 1 1 1 1 1 \textbf{3 3} 1~

~1 1 1 1 1 1 1 \textbf{2 2} 1~

~\textbf{1 1 1 1 1 1 1 1 1 1}~

~0 0 0 0 0 0 0 0 0 0~

Subtasks

~40\%~ số điểm ứng với các test có ~n ≤ 1000~

~30\%~ số điểm ứng với các test có ~n ≤ 10^5~

~30\%~ số điểm không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề