Cho dãy số nguyên dương A gồm N phần tử ~A_i~ (~1 \le i \le N~; ~3 \le N \le 10^6~; ~1 \le A_i \le 2.10^9~) và biểu thức ~M = A_i – 3A_j + 2A_k~ với ~A_i~, ~A_j~, ~A_k~ thuộc dãy số A (~1 \le i < j < k < N~).

Yêu cầu: Tìm giá trị M lớn nhất.

Input:

• Dòng 1: Ghi số nguyên dương N.
• Dòng 2: Ghi N số nguyên dương ~Ai~, mỗi số cách nhau một khoảng trống.

Output:

• Dòng 1: Ghi ra số M tìm được.

Example:

Input:

5
8 1 2 6 3

Output:

17

Constraints:

• Có 70% số lượng bộ test tương ứng với ~3 < N \le 300~; ~1 \le A_i \le 65535~
• Có 30% số lượng bộ test tương ứng với ~300 < N \le 10^6~; ~1 \le A_i \le 2.10^9~