LCK mùa hè

Có thể nhận thấy ở thời điểm hiện tại, ngành công nghiệp game Esport ngày càng phát triển. Khi nói đến tựa game Esport nổi tiếng và hấp dẫn nhất, không thể thiếu Liên Minh Huyền Thoại (League of Legends). Với mức độ phủ sóng khủng khiếp trên toàn cầu nên các giải đấu về trò chơi này luôn nhận được sự quan tâm của đông đảo người hâm mộ. Và giải đấu LCK cũng là một trong số đó.

LCK là viết tắt của League of Legends Champions Korea, trước đây được biết đến với tên Ongamenet LCK (OGN) và được tổ chức bởi 1Ongamenet, là đấu trường cao nhất của bộ môn thể thao điện tử Liên Minh Huyền Thoại tại Hàn Quốc". Hiện tại, LCK mùa hè \(2023\) đã chính thức khép lại với chiến thắng không thể bàn cãi của GenG.

Fekar - một trong những tuyển thủ huyền thoại của làng Liên Minh Huyền Thoại, sau một thời gian dài gắn bó đã giải nghệ. Fekar đã được đề cử lên làm trưởng ban tổ chức của giải đấu LCK. Vì một lí do nào đó, Fekar đã thay đổi cơ cấu của giải đấu này như sau:

Trước khi bắt đầu mùa giải, mỗi tuyển thủ đều sẽ có một huy hiệu hiển thị một số nguyên \(h_{i}\) - đại diện cho chỉ số kĩ năng của tuyển thủ đó (với \(i\) là số hiệu của tuyển thủ, có tất cả \(n\) tuyển thủ tham gia thi đấu). Thay vì thi đấu theo đội tuyển của mình với hình thức \(5\) vs \(5\), Fekar đã thay đổi luật, tất cả các tuyển thủ sẽ không theo một đội tuyển nào, xếp các tuyển thủ từ trái sang phải theo thứ tự từ \(1\) đến \(n\), sau đó sẽ chia lại các đội tuyển thi đấu (đồng nghĩa rằng bạn sẽ không biết đồng đội của bạn là ai). Fekar yêu cầu các tuyển thủ thuộc cùng một đội tuyển phải đứng sát nhau, một tuyển thủ phải thuộc chính xác một đội tuyển. Nói cách khác, một đội tuyển thi đấu sẽ là một đoạn con trên dãy các tuyển thủ. Quy định này sẽ không hạn chế người của một đội tuyển.

Fekar quy định sức mạnh của một đội tuyển là sự chênh lệnh giữa tuyển thủ có chỉ số kĩ năng cao nhất và tuyển thủ có chỉ số kĩ năng thấp nhất. Nói một cách "công thức" hơn,
nếu tuyển thủ đầu tiên của đội tuyển \(X\) có số thứ tự là \(i\), và tuyển thủ cuối cùng có số thứ tự là \(j\) \((1 \leq i \leq j \leq n)\), sức mạnh đội tuyển là giá trị \(max(h_{i}...h_{j}) - min(h_{i}...h_{j})\).

Gọi sức mạnh tổng thể của giải đấu là tổng sức mạnh của các đội tuyển, Fekar muốn giá trị này đạt càng lớn càng tốt, các bạn hãy giúp Fekar chia đội tuyển một cách hợp lí nhé!

Input

Dòng đầu tiên là số nguyên \(n\) - số tuyển thủ thi đấu \((2 \leq n \leq 10^6)\).

Dòng tiếp theo là \(n\) số nguyên \(h_{1}, h_{2}, h_{3}, ..., h_{n}\) \((-10^9 \leq h_{i} \leq 10^9)\).

Output

Kết quả bài toán.

Example

5
1 2 3 1 2

3

Scoring

\(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 20\).

\(20\%\) số test tương ứng với \(20\%\) số điểm, \(h_{i} <= h_{i + 1}\) \((1 \leq i < n)\).

\(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 5000\).

\(20\%\) số test tương ứng với \(20\%\) số test, \(h_{i} = a\) hoặc \(h_{i} = b\) với \(a, b\) là hằng số.

\(20\%\) số test còn lại không có ràng buộc gì thêm.