크기가 N인 배열 A가 주어졌을 때, i < j < k < l을 만족하는 (i, j, k, l) 중에서 A[j]-A[i]+A[l]-A[k]의 최댓값을 구하는 프로그램을 작성하시오. 

입력 형식

첫째 줄에 배열 A의 크기 N(4 ≤ N ≤ 1,000,000)이 주어진다.</p>

둘째 줄에는 배열 A에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1,000,000보다 작거나 같은 자연수이다.

출력 형식

첫째 줄에 i < j < k < l을 만족하는 (i, j, k, l) 중에서 A[j]-A[i]+A[l]-A[k]의 최댓값을 출력한다.

예제 입력 1

5
1 2 3 4 5

예제 출력 1

3

예제 입력 2

5
1 1 1 1 1

예제 출력 2

0

예제 입력 3

6
1 2 1 2 1 2

예제 출력 3

2

예제 입력 4

8
9 1 8 2 7 3 6 4

예제 출력 4

12

예제 입력 5

4
9 8 3 2

예제 출력 5

-2