Исправление кучи

Дана max-куча с n числами, в которой все элементы, кроме корня, уже удовлетворяют свойству max-кучи. Ваша задача — исправить кучу, чтобы все её элементы действительно соответствовали данному свойству.

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

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

Во второй строке приведены n чисел (), которые представляют значения элементов в куче.

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

Программа должна вывести n чисел, разделённых пробелами, представляющих исправленную кучу.

Примеры

Пояснение