Buôn cỏ

Vậy là Đại hội võ lâm đã bế mạc, các võ sĩ lại chia tay nhau mỗi người một ngả. Dế Mèn và Dế Trũi mỗi người một ngựa tung tăng về quê nhà.

Đường về quê của hai võ sĩ phải đi qua lần lượt $n$ ngôi làng được đánh số từ $1$ đến $n$. Hiện tại, họ đang ở làng $1$, quê nhà của họ là làng thứ $n$. Để có thêm lộ phí, hai võ sĩ cần lập kế hoạch mua, bán cỏ tại các ngôi làng trên đường họ trở về. Tại ngôi làng thứ $i$ giá mua vào, bán ra một bao cỏ là $a_i$ đồng. Biết rằng, mỗi ngựa tại một thời điểm chỉ thồ được nhiều nhất một bao cỏ (nên hai võ sĩ mang theo nhiều nhất $2$ bao cỏ cùng lúc) và tại mỗi ngôi làng chỉ được phép mua hoặc bán nhiều nhất một bao cỏ (tính chung cho cả hai võ sĩ). Chỉ được bán bao cỏ đang mang theo; bao cỏ còn lại khi về tới làng $n$ không được tính tiền.

Yêu cầu: Tính số tiền lãi nhiều nhất mà hai võ sĩ Dế Mèn và Dế Trũi có thể kiếm được nhờ việc mua, bán cỏ trên hành trình trở về quê nhà.

Dữ liệu vào

• 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)$.

Dữ liệu ra

In ra một số nguyên duy nhất là số tiền lãi lớn nhất mà hai võ sĩ có thể kiếm được nhờ việc buôn cỏ.

Ràng buộc

• $1\le n\le {10}^6$.
• $1\le a_i\le {10}^9$ với $1\le i\le n$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($20\%$ số test): $1\le n\le 20$.
• Subtask 2 ($20\%$ số test): $a_i=i$ với $1\le i\le n$.
• Subtask 3 ($30\%$ số test): $n\le 1000$.
• Subtask 4 ($30\%$ số test): không có thêm ràng buộc gì.

Ví dụ