Cho một dãy gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Bạn cần thực hiện các bước sau theo đúng thứ tự:

1. Chọn một chỉ số ~k~ (~1 \le k \le n-1~).
2. Chia dãy số trên thành hai phần: ~a_1, a_2, \dots, a_k~ và ~a_{k+1}, a_{k+2}, \dots, a_n~.
3. Loại bỏ một phần tử duy nhất từ mỗi phần.

Gọi ~c~ là tổng các phần tử của phần kết quả thứ nhất (sau khi loại bỏ) và ~d~ là tổng các phần tử của phần kết quả thứ hai (sau khi loại bỏ). Nhiệm vụ của bạn là tìm giá trị lớn nhất có thể của ~|c-d|~. Nói cách khác, tìm chênh lệch lớn nhất của hai phần sau khi thực hiện các bước trên.

Bạn có thể coi tổng của phần rỗng bằng 0 (nếu sau khi loại bỏ phần nào đó trở nên rỗng).

Dữ liệu

• Dòng đầu: một số nguyên ~n~ (~2 \le n \le 10^5~) là số phần tử của dãy.
• Dòng thứ hai: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~-10^3 \le a_i \le 10^3~).

Kết quả

• Một số nguyên duy nhất là giá trị lớn nhất có thể của ~|c-d|~ sau khi thực hiện các bước như mô tả.

Ví dụ

Ví dụ 1

Input

2
-1 2

Output

0

Ví dụ 2

Input

4
2 -5 4 -7

Output

12

Giới hạn

• Subtask 1 (10% số điểm): ~n \le 3~.
• Subtask 2 (30% số điểm): ~a_i = a_j~, ~1 \le i, j \le n~.
• Subtask 3 (30% số điểm): ~n \le 300~.
• Subtask 4 (30% số điểm): không có ràng buộc gì thêm.