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

Input

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

Output

• 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ả.

Example

2
-1 2

0

4
2 -5 4 -7

12

Scoring

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