Trước tình hình cấp bách tại Myanmar sau trận động đất, chiến dịch hỗ trợ nhân đạo của Việt Nam đã chính thức được triển khai. Hai đoàn xe vận tải chủ lực, Đoàn 1 và Đoàn 2, được giao nhiệm vụ vận chuyển hàng cứu trợ đến người dân gặp nạn. Mục tiêu cao nhất là đưa được càng nhiều hàng cứu trợ càng tốt đến những khu vực cần thiết nhất.

Tuyến đường cứu trợ đi qua ~n~ điểm điều phối được đánh số từ 1 đến ~n~. Tại mỗi điểm ~i~, có một chỉ số ~a[i]~ phản ánh mức độ khó khăn trong tiếp cận và/hoặc mức độ ưu tiên về nhu cầu tại điểm đó. Chỉ số ~a[i]~ thấp có thể nghĩa là điểm dễ tiếp cận hoặc nhu cầu ít khẩn cấp hơn, trong khi ~a[i]~ cao nghĩa là điểm khó tiếp cận hơn và/hoặc nhu cầu rất cấp thiết.

Để tối đa hóa hiệu quả cứu trợ (vừa đảm bảo số lượng, vừa ưu tiên nơi cần), các đoàn xe áp dụng chiến lược: ưu tiên thực hiện những lượt vận chuyển mang lại "Giá trị Ưu tiên Tăng thêm" cao nhất. Một lượt vận chuyển hàng từ điểm ~i~ đến điểm ~j~ (~j > i~) được coi là có giá trị ưu tiên tăng thêm là ~a[j] - a[i]~. Giá trị này dương thể hiện việc đã thành công chuyển hàng từ nơi ít ưu tiên/dễ dàng hơn đến nơi ưu tiên cao/khó khăn hơn.

• Tiếp nhận hàng tại điểm ~i~: Bắt đầu một lượt vận chuyển từ điểm có chỉ số ~a[i]~.
• Phân phát hàng tại điểm ~j~: Hoàn thành lượt vận chuyển tại điểm có chỉ số ~a[j]~.
• Giới hạn: Mỗi đoàn xe chỉ chở được 1 đơn vị hàng tại một thời điểm và chỉ thực hiện 1 hành động (tiếp nhận hoặc phân phát) tại mỗi điểm.

Yêu cầu: Tính tổng "Giá trị Ưu tiên Tăng thêm" lớn nhất mà hai Đoàn 1 và Đoàn 2 có thể cùng nhau đạt được trên suốt hành trình.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ (~1 \le n \le 10^6~);
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~a_i \le 10^9~ với ~1 \le i \le n~).

Output

• Ghi ra một số nguyên duy nhất là tổng "Giá trị Ưu tiên Tăng thêm" lớn nhất đạt được.