Problem description
Krasnal Wrocek ma ciąg A składający się z N liczb. Chce podzielić go na cztery niepuste i spójne fragmenty: B, C, D oraz E.
Niech P, Q, R, S oznaczają sumy elementów odpowiednio w ciągach B, C, D, E. Wrocek jest szczęśliwszy, gdy różnica pomiędzy największą i najmniejszą z tych sum jest jak najmniejsza.
Pomóż mu i znajdź najmniejszą możliwą wartość tej różnicy.
Wejście
W pierwszym wierszu wejścia znajduje się liczba naturalna N, oznaczająca długość ciągu.
W drugim wierszu wejścia znajduje się N liczb naturalnych Ai, opisujących ciąg krasnala Wrocka.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć najmniejsza możliwa różnica pomiędzy maksimum i minimum liczb P, Q, R, S.
Ograniczenia
4 ≤ N ≤ 200 000, 1 ≤ Ai ≤ 109.
Przykłady
| Wejście |
|
| Wyjście |
|
| Wyjaśnienie |
Jeżeli podzielimy ciąg A na ciągi B, C, D, E = (3), (2), (4), (1,2), to ich sumy wynoszą kolejno P = 3, Q = 2, R = 4, S = 3. Największa i najmniejsza z tych wartości to 4 i 2, z różnicą 2. Można wykazać, że nie istnieje podział dający mniejszą różnicę. |
| Wejście |
|
| Wyjście |
|
| Wejście |
|
| Wyjście |
|