Cho dãy gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Ta xét biểu thức có dấu cộng và dấu trừ xen kẽ, bắt đầu bằng dấu cộng ở số hạng đầu:

~S = a_1 - a_2 + a_3 - a_4 + a_5 - \dots + (-1)^{n-1} \times a_n~

Nói cách khác, số hạng ở vị trí lẻ được cộng, số hạng ở vị trí chẵn bị trừ.

Bạn phải thực hiện đúng một phép đổi chỗ hai số hạng trong dãy (đổi chỗ giá trị của hai vị trí, còn dấu của từng vị trí giữ nguyên) sao cho giá trị ~S~ thu được là lớn nhất có thể. Hãy in ra giá trị lớn nhất đó.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~n~ (~1 \le n \le 10^5~) là số số hạng.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~|a_i| \le 10^9~).

Kết quả

• In ra một số nguyên là giá trị lớn nhất của ~S~ sau khi thực hiện phép đổi chỗ hai số hạng.

Ví dụ

EXP.INP

6
2 5 4 7 9 1

EXP.OUT

12