Tuấn tiếp tục chơi vòng hai của trò chơi xếp bi.

Ở vòng hai, có $K$ viên bi xếp thành một hàng, được đánh số từ $1$ đến $K$ từ trái sang phải. Lúc đầu, trên viên bi thứ $i$ $(1 \leq i \leq K)$ gắn số $a_i$. Trong mỗi bước chơi ở vòng này, người chơi phải chọn một viên bi gắn số $Y$ ở vị trí từ $2$ đến $K$ và đẩy nó sang trái. Viên bi bắt đầu di chuyển cho đến khi va chạm với một viên bi nằm bên trái, hai viên bi này hợp nhất thành một viên bi mới gắn số $X - Y$, với $X$ là số gắn trên viên bi bên trái đã va chạm với viên bi gắn số $Y$. Sau $K - 1$ lần đẩy, chỉ còn lại một viên bi. Số điểm đạt được ở vòng hai là số gắn trên viên bi cuối cùng còn lại.

Yêu cầu: Viết chương trình cho biết số điểm lớn nhất mà Tuấn đạt được ở vòng hai.

Dữ liệu vào

• Dòng đầu chứa số nguyên $K$ ~(2 \leq K \leq 10^5)~ là số viên bi ở vòng hai.
• Dòng thứ hai chứa $K$ số nguyên ~a_1, a_2, \dots, a_K~ ~(-10^9 \leq a_i \leq 10^9; 1 \leq i \leq K)~ biểu thị số trên các viên bi, các số cách nhau bởi dấu cách.

Kết quả ra

• Một số nguyên duy nhất là số điểm lớn nhất đạt được ở vòng hai.

Ví dụ 1

Dữ liệu

3
3 1 2

Kết quả

4

Giải thích

Có 2 thứ tự đẩy bi. Thứ tự tốt nhất là viên thứ $3$, rồi viên thứ $2$: Sau lần đẩy đầu tiên, số trên các viên bi trở thành $3, -1$. Sau lần đẩy cuối cùng, còn lại viên bi có giá trị là $4$.

Ví dụ 2

Dữ liệu

8
5 8 2 -9 7 -9 4 7

Kết quả

35