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

Yêu cầu: 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ả.

Scoring

Sample Input 1

2
-1 2

Sample Output 1

0

Sample Input 2

4
2 5 -4 -7

Sample Output 2

12