Elevi Pentru Elevi Arges - IX | Desert

Andrei este pofticios. După ce a mâncat primele feluri, acesta vrea să își pregătească trei torturi, dintre care va mânca doar unul la întâmplare.

Un tort va fi alcătuit din mai multe sortimente de ciocolată. Definim greutatea unui astfel de tort ca fiind suma gramajelor sortimentelor de ciocolată folosite, adică un tort alcătuit din $20$ grame de ciocolată albă și $30$ grame de ciocolată neagră va avea greutatea de $50$ de grame.

Andrei are la dispoziție $N$ sortimente de ciocolată, dispuse în linie pe un raft din cămara sa, fiecare având un număr de ordine.

• Pentru primul tort, băiatul va folosi toate sortimentele de la primul până la un anumit număr de ordine $A$, ales de acesta;
• Pentru al doilea tort, va folosi toate sortimentele de la numărul de ordine $A + 1$ până la un anumit număr de ordine $B$, ales de acesta;
• Pentru al treilea tort, va folosi toate sortimentele de la numărul de ordine $B + 1$ până la ultimul sortiment.

Cum tortul pe care îl va mânca băiatul este selectat la întâmplare, Andrei vrea să se asigure că se va sătura alegând oricare dintre cele trei torturi, așa că își propune să minimizeze diferența dintre greutatea celui mai "greu" tort și greutatea celui mai "ușor" tort.

Altfel spus, notând greutatea celor trei torturi cu T1, T2, T3, Andrei vrea ca expresia următoare, numită eroarea rețetei, să fie cât mai mică:

max(T1, T2, T3) - min(T1, T2, T3)

Cerință

Dându-se cele $N$ sortimente de ciocolată și gramajul fiecăruia, aflați cea mai mică eroare a rețetei posibilă, ajutându-l pe Andrei să aleagă cele două poziții/numere de ordine $A$ și $B$.

Date de intrare

Pe prima linie a fișierului de intrare desert.in se va afla numărul $N$.

Pe a doua linie se vor afla gramajele celor $N$ sortimente de ciocolată de pe raft.

Date de ieșire

Pe prima linie a fișierului de ieșire desert.out se va afișa eroarea minimă a rețetei.

Restricții și precizări

• $3 \le N \le 2 \cdot 10^5$
• $1 \le$ gramajul oricărui sortiment de ciocolată $\le 10^4$
• Se acordă $10$ puncte din oficiu.

Exemplu

desert.in

10
8 16 11 1 5 20 14 20 7 5

desert.out

7

Explicație

Putem alege $A = 4$ și $B = 7$, iar torturile vor arăta in felul următor:

Astfel, primul tort va conține sortimentele de la $1$ la $4$, având greutatea $8 + 16 + 11 + 1 = 36$.
Al doilea tort va conține sortimentele de la $5$ la $7$, având greutatea $5 + 20 + 14 = 39$.
Al treilea tort va conține sortimentele de la 8 la 10, având greutatea $20 + 7 + 5 = 32$.
În acest caz, eroarea rețetei este $\max(36, 39, 32) - \min(36, 39, 32) = 39 - 32 = 7$. Se poate demonstra faptul că răspunsul este optim.