Зеник-бізнесмен

Limits: 2 sec., 256 MiB

Зеник, як нiхто iнший знає, що найлегший спосiб багато заробляти у IТ — це заснувати власну аутсорс компанію.

Оскільки Зеник дуже добре вміє продавати сумнівні можливості, у нього вже з’явилось \(n\) кандидатів, \(i\)-ому з яких вже запропонували зарплату \(a_i\). Більше того, Зеник вже встиг знайти великого замовника — компанію “Абетка”, яка не рахує гроші, але дуже сильно переймається за рівноправ’я всередині Зеникової компанії. Тому, всупереч здоровому глузду, “Абетка” не звертає уваги на витрачені гроші та хоче мінімізувати нерівність — різницю між найбільш та найменш оплачуваними працівниками.

Звісно, що в душі Зеник розуміє, що така політика, мабуть, доведе “Абетку” до банкрутства, але вирішив скористатися цією вразливістю. Оскільки компанія Зеника, як справжня аутсорс компанія, бере певний відсоток від зарплати працівників собі, то Зенику немає сенсу зменшувати зарплати кандидатам. Тому, аби задовольнити замовника, запропоновані зарплати він буде змінювати таким чином — довільну кількість разів вибере якогось кандидата, та подвоїть йому зарплату (причому одного і того ж кандидата він може вибирати довільну кількість разів).

Проте поки головне питання залишилось нез’ясованим — скільки саме працівників Зенику потрібно найняти? Тому він для кожного числа \(i\) від \(1\) до \(n\) просить Вас дізнатися яку найменшу нерівність можна отримати, якщо працевлаштувати перших \(i\) кандидатів у списку.

Input

У першому рядку задано натуральне число \(n\) — кількість кандидатів у Зеникову компанію.

У другому рядку задано \(n\) натуральних чисел — початкові зарплати для кожного з цих кандидатів.

Output

Виведіть \(n\) чисел через пробіл — які мінімальні нерівності у зарплаті може досягнути Зеник, найнявши перших \(i\) кандидатів.

Constraints

\(1 \le n \le 10^5\),

\(1 \le a_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 4 7 3 33	0 1 2 9

Notes

Розглянемо приклад.

Якщо Зеник найме лише першу людину, то скільки б він не платив їй, нерівність буде \(0\).

Якщо Зеник найме людей з зарплатами \(4\) i \(7\), то оптимально буде подвоїти зарплату першому і отримати нерівність \(1\).

Якщо Зеник найме людей з зарплатами \(4\), \(7\) і \(3\), то оптимально буде подвоїти зарплату першому та третьому і отримати нерівність \(2\).

Якщо ж Зеник вирішить найняти всіх людей, то оптимально буде тричі подвоїти зарплату першому і третьому, двічі — другому, та залишити без змін зарплату четвертому кандидату. Таким чином кінцеві зарплати будуть \(32, 28, 24, 33\), a нерівність становитиме \(33 - 24 = 9\).