Задан массив из 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.

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

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