Dãy số

Cho một dãy số \(A\) gồm \(n\) phần tử số nguyên có dạng \(a_1, a_2, \ldots, a_n\). Gọi \(W\) là tổng giá trị của \(n - 1\) phần tử được chọn ra trong \(A\). Mỗi lần chọn một phần tử trong hai phần tử đầu tiên và thực hiện theo quy tắc sau:

• Nếu chọn \(a_1\) thì \(W = W + a_1\), sau đó lấy \(a_1\) ra khỏi dãy thì phần tử \(a_2\) lúc này là \(a_1\), phần tử \(a_3\) là \(a_2\), ...

• Ngược lại, nếu chọn \(a_2\) thì \(W = W - a_2\), sau đó lấy \(a_2\) ra khỏi dãy thì phần tử \(a_3\) lúc này là \(a_2\), phần tử \(a_4\) là \(a_3\), ...
  Ban đầu \(W = 0\).

Yêu cầu: Hãy lặp lại quy tắc trên một cách tối ưu, xác định giá trị \(W\) lớn nhất khi chọn ra đúng \(n - 1\) phần tử.

Input

Dữ liệu vào có cấu trúc như sau:

• Dòng đầu tiên ghi số \(n\) (\(2 \le n \le 10^5\)).

• Dòng tiếp theo ghi các số \(a_i\) (\(|a_i| \le 10^4\)), mỗi số cách nhau bởi một dấu cách.

Ràng buộc dữ liệu vào:

• \(30\%\) số test tương ứng với số điểm có \(a_i > 0\).

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

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

Output

In ra một số nguyên là kết quả tìm được.

Example

Input:

4
1 2 -3 2

Output:

6

Note

Thứ tự chọn tối ưu như sau: \(W = 1 - (-3) + 2 = 6\).