C. Четыре отрезка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив из n целых чисел. Пусть sum(l, r) — сумма чисел на индексах с l по r не включительно (l-й элемент учитывается, r-й элемент не учитывается). Индексы l и r таковы, что 0 ≤ l ≤ r ≤ n. Индексы в массиве нумеруются с 0.

Например, если массив a = [ - 5, 3, 9, 4], то sum(0, 1) =  - 5, sum(0, 2) =  - 2, sum(1, 4) = 16, и sum(i, i) = 0 для всех i от 0 до 4.

Выберите три индекса delim0, delim1, delim2 (0 ≤ delim0 ≤ delim1 ≤ delim2 ≤ n) и поделите массив таким образом, чтобы величина res = sum(0, delim0) - sum(delim0, delim1) + sum(delim1, delim2) - sum(delim2, n) была максимальна.

Обратите внимание, что некоторые значения sum(l, r) могут соответствовать пустым отрезкам (если l = r для соответствующего отрезка).

Входные данные

В первой строке записано одно целое число n (1 ≤ n ≤ 5000).

Во второй строке записаны n целых чисел a0, a1, ..., an - 1 ( - 109 ≤ ai ≤ 109).

Выходные данные

Выведите три таких индекса, что величина res — максимальна. Если существует несколько ответов, выведите любой из них.

Примеры
Входные данные
3
-1 2 3
Выходные данные
0 1 3
Входные данные
4
0 0 -1 0
Выходные данные
0 0 0
Входные данные
1
10000
Выходные данные
1 1 1