A[j]-A[i]+A[l]-A[k]의 최댓값

시간 제한2초메모리 제한512 MB

요약

배열에서 i<j<k<l인 네 인덱스를 골라 A[j]-A[i]+A[l]-A[k]의 최댓값을 구한다.

문제

크기가 $N$ 인 배열 $A$ 가 주어진다. 배열의 인덱스는 1부터 $N$ 까지이다.

$i < j < k < l$ 을 만족하는 인덱스 네 개 $(i, j, k, l)$ 중에서 $A[j] - A[i] + A[l] - A[k]$ 의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 배열 $A$ 의 크기 $N$ 이 주어진다. ( $4 \le N \le 10^6$ )

둘째 줄에 배열 $A$ 의 원소가 순서대로 주어진다. 각 원소는 $10^6$ 이하의 자연수이다.

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