Problem Statement

Snuke có một chuỗi số nguyên ~A~ có chiều dài ~N~ .

Anh ấy sẽ thực hiện ba lần cắt giảm trong ~A~ và chia nó thành 4 (không rỗng) tiếp giáp với các chuỗi con ~B, C, D~ và ~E~ . Các vị trí các nút cắt có thể được tự do chọn.

Cho ~P,Q,R,S~ là tổng của các phần tử trong ~B,C,D,E~ , tương ứng. Snuke cảm thấy hạnh phúc khi sự khác biệt tuyệt đối của tối đa và tối thiểu giữa ~P,Q,R,S~ là nhỏ nhất. Tìm sự khác biệc tuyệt đối tối đa và tối thiểu giữa ~P,Q,R,S~

Ràng buộc

• ~4 \leq N \leq 2 \times 10^5~
• ~1 \leq A_i \leq 10^9~
• Tất cả các giá trị đầu vào là số nguyên.

Input

Đầu vào tiêu chuẩn theo định dạng sau:

~N~

~A_1~ ~A_2~ ~...~ ~A_N~

Output

Tìm sự khác biệt tuyệt đối tối đa và tối thiểu giữa ~P,Q,R,S~

Sample Input 1

5
3 2 4 1 2

Sample Output 1

2

Nếu chúng chia cho ~A~ như ~B,C,D,E=(3),(2),(4),(1,2)~ , sau đó ~P=3,Q=2,R=4,S=1+2=3~ . Ở đây, giá trị tối đa và tối thiểu giữa ~P,Q,R,S~ là ~4~ và ~2~ , với sự khác biệt tuyệt đối là ~2~ . Chúng tôi không thể tạo ra sự khác biệt tuyệt đối của mức tối đa và mức tối thiểu nhỏ hơn 2 , vì vậy câu trả lời là 2.

Sample Input 2

10
10 71 84 33 6 47 23 25 52 64

Sample Output 2

36

Sample Input 3

7
1 2 3 1000000000 4 5 6

Sample Output 3

999999994