Vào sáng ngày \(24/06/2025\), khi các bạn học sinh được giải Nhất bảng \(B\) thành phố Đà Nẵng đang nghe giảng, thì bùm một cái, con quái vật với thân hình là Tung Tung Tung Sahur, tự xưng là người hơn Nguyễn Nhân Danh thêm một chữ k đã tấn công vào trụ sở. Nhận thấy điềm chẳng lành, anh Hiếu đang dạy đã vội vã dùng thuật toán để tìm đường đi ngắn nhất chạy thoát, các học sinh khác cũng đã chạy trốn, chỉ còn lại mình Sĩ Quý với thuật toán tham lam mà không tìm được đường ra. May thay, Quý đã nhận ra được quy luật.

Con đường chạy thoát của Quý được biểu diễn dưới một mảng \(A\) gồm \(n\) số tự nhiên, với \(A_i\) là độ cao của tòa nhà thứ \(i\). Con quái vật có thể chọn một đoạn con liên tiếp từ \(l\) đến \(r\) có độ dài từ \(2\) trở lên, và biến tất cả các tòa nhà trong đó thành chênh lệch độ cao giữa \(A_l\) và \(A_r\). Mục tiêu của con quái vật là biến tất cả các tòa nhà sao cho tổng độ cao là lớn nhất. Nhận được tin, mọi người cố gắng tìm ra đáp án để giải cứu Quý. Bạn là một trong những giải Nhất bảng \(B\) (tương lai), hãy cố gắng tìm ra tổng mảng \(A\) lớn nhất.

Input

• Dòng đầu tiên chứa số tự nhiên \(n\) \((2 \leq n \leq 2 \times 10^5)\).
• Dòng thứ hai chứa dãy số tự nhiên \(A\) \((1 \leq A_i \leq 10^9)\) gồm \(n\) phần tử cách nhau bằng dấu cách.

Output

• In ra một dòng là tổng mảng \(A\) lớn nhất.

Scoring

• \(20\%\) số điểm có \(n=2\).
• \(20\%\) số điểm có \(n=3\).
• \(30\%\) số điểm có \(n \leq 10^3\)
• \(30\%\) số điểm không có ràng buộc gì thêm

Example

3
3 5 9

27