cho.sh

Maximum of A[j]-A[i]+A[l]-A[k]

Given an array, choose four increasing indices i<j<k<l maximizing A[j]-A[i]+A[l]-A[k].

Medium4Dynamic programmingArrayBrute forceNo attempts yetTime limit2sMemory limit512 MB

Problem

You are given an array AA of size NN. The indices of the array run from 1 to NN.

Write a program that finds the maximum value of A[j]−A[i]+A[l]−A[k]A[j] - A[i] + A[l] - A[k] over all index quadruples (i,j,k,l)(i, j, k, l) with i<j<k<li < j < k < l.

Input

The first line contains the size NN of the array AA. (4≤N≤1064 \le N \le 10^6)

The second line contains the elements of AA in order. Every element is a natural number not greater than 10610^6.

Output

Print the maximum value of A[j]−A[i]+A[l]−A[k]A[j] - A[i] + A[l] - A[k] over all (i,j,k,l)(i, j, k, l) with i<j<k<li < j < k < l. This value can be negative.