Рекурсивное дерево отрезков

Вам дан массив из n элементов. Нужно рекурсивно построить дерево отрезков (segment tree) и вычислить значение каждого узла в этом дереве. Значение каждого узла соответствует сумме подмассива, за который этот узел отвечает.

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

В первой строке содержится целое число n (1 ≤ n ≤ 100 000) — количество элементов в массиве.

Во второй строке заданы n целых чисел (), разделённые пробелами.

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

Выведите построенное дерево отрезков, указав значение каждого узла. Каждый уровень дерева следует выводить в отдельной строке, а внутри строки значения узлов должны быть разделены пробелом.

Примеры