Cho dãy gồm N ~(1 \le N \le 10^5)~ số nguyên ~A_1, A_2, A_N; (0 < A_i \le 10^5)~. Với bộ ba số (i,j,k) trong đó ~1 \le i < j < k \le N~ hãy tìm giá trị ~S= 3A_i - A_j - A_k~ sao cho S đạt giá trị lớn nhất.

Input:

Được cho bởi tệp upmax.inp có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên N.
• Dòng thứ hai chứa N số nguyên ~A_1, A_2,..., A_N~ giữa các số cách nhau một khoảng trắng.

Output:

Được cho bởi tệp upmax.out có cấu trúc như sau:

• In ra một số duy nhất là số S lớn nhất tìm được.

Example

Input

9
95 5 74 65 89 62 3 2 37 

Output

280