Under construction

Still being built. Things may change

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

Time limit2sMemory limit512 MB

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

Medium4 of 10

Topics
Dynamic programming, Array, Brute force
Solved
No attempts yet

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.

Examples5

  1. Example 1

    Input
    5
1 2 3 4 5
    Expected output
    3

  2. Example 2

    Input
    5
1 1 1 1 1
    Expected output
    0

  3. Example 3

    Input
    6
1 2 1 2 1 2
    Expected output
    2

  4. Example 4

    Input
    8
9 1 8 2 7 3 6 4
    Expected output
    12

  5. Example 5

    Input
    4
9 8 3 2
    Expected output
    -2