Se consideră un sir de numere naturale a₁,a₂,...,a_n.

Cerinţă

Să se determine suma maximă a unei expresii (a_i-a_j)+(a_k-a_p), unde 1 <= i < j < k < p <= n.

Date de intrare

Fişierul de intrare sir2dif.in conţine pe prima linie numărul natural n. Pe a doua linie, separate prin câte un spatiu, se află numerele naturale a₁,a₂,...,a_n.

Date de ieşire

Fişierul de ieşire sir2dif.out va conţine pe prima linie un singur număr natural reprezentând suma maximă posibilă a unei expresii (a_i-a_j)+(a_k-a_p), unde i < j < k < p.

Restricţii

• 4 <= n <= 100 000
• 0 <= a_i <=10⁶, pentru orice i = 1..n
• pentru 50% din teste, n <= 5000

Exemplu

sir2dif.in	sir2dif.out	Explicaţii
8 1 8 5 3 7 4 6 9	8	Luând cele patru elemente de la pozitiile i=2, j=4, k=5, p=6 se obtine suma maximă: (8-3)+(7-4)=8
sir2dif.in	sir2dif.out	Explicaţii
4 3 2 1 4	-2	(3-2)+(1-4) = -2

prof. Dan Pracsiu

Liceul "Stefan Procopiu" Vaslui

dpracsiu@yahoo.com