Біговий клуб набирає учасників і швидко зростає: щодня до нього приєднується рівно один новий учасник. Кожен учасник приходить із певним початковим рівнем майстерності та отримує унікальний ідентифікатор відповідно до порядку своєї появи.

Наприкінці кожного дня Тренер любить обчислювати показник, який він називає «загальним потенціалом» клубу. Це значення є просто сумою індивідуальних потенціалів усіх поточних учасників. Щоб підтримувати мотивацію учасників, потенціал кожного з них обчислюється через гіпотетичний сценарій «що, якби», який передбачає одне інтенсивне тренування.

У цьому уявному тренуванні учасник може докласти певну кількість зусиль, щоб тимчасово підвищити свій рівень майстерності. За кожну $1$ одиницю витрачених зусиль його рівень майстерності збільшується рівно на $1$ одиницю. Натомість він отримує $1$ одиницю «щастя» за кожного іншого поточного учасника клубу, який:

• приєднався до клубу строго пізніше за нього; і
• спочатку мав рівень майстерності строго вищий за його власний, але тепер його наздогнали або перевершили завдяки тренуванню.

Зауважте, що під час цього обчислення підвищується рівень майстерності лише цього учасника, тоді як рівні майстерності всіх інших учасників залишаються незмінними на своїх початкових значеннях.

Потенціал одного учасника визначається як максимально можливе значення його чистого здобутку (щастя мінус зусилля), якого він міг би досягти за оптимального вибору рівня зусиль. Ці тренування є цілком теоретичними; вони використовуються лише для щоденного звіту Тренера, а фактичні рівні майстерності учасників день у день залишаються незмінними.

Ваше завдання — допомогти Тренеру обчислити загальний потенціал клубу наприкінці кожного дня періоду набору.

Вхідні дані

Перший рядок вхідних даних містить ціле число $n$ ($1 \le n \le 10^5$), що позначає кількість днів, протягом яких клуб набирає учасників.

Другий рядок містить $n$ цілих чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), де $a_i$ — початковий рівень майстерності учасника, який приєднується в день $i$.

Вихідні дані

Виведіть $n$ цілих чисел в одному рядку. $k$-те ціле число повинно дорівнювати загальному потенціалу клубу наприкінці дня $k$.

Приклади

Вхідні дані 1

8
1 2 3 1 2 3 2 3

Вихідні дані 1

0 0 0 0 1 3 5 9

Вхідні дані 2

1
1

Вихідні дані 2

0

Примітка

Пояснення до прикладу 1: У день $5$ є $5$ учасників із рівнями майстерності $[1, 2, 3, 1, 2]$. Для учасника $1$: Є $3$ учасники, які приєдналися пізніше зі строго вищою майстерністю: учасник $2$, учасник $3$ та учасник $5$. Максимальний потенціал учасника $1$ дорівнює $1$ і досягається будь-якою з таких стратегій:

• Якщо учасник $1$ витратить $1$ одиницю зусиль, його майстерність стане рівною $2$. Він наздожене або перевершить учасника $2$ та учасника $5$. Щастя становить $2$ одиниці, а здобуток — $2 - 1 = 1$ одиницю.
• Якщо учасник $1$ витратить $2$ одиниці зусиль, його майстерність стане рівною $3$. Він наздожене або перевершить учасників $2$, $3$ та $5$. Щастя становить $3$ одиниці, а здобуток — $3 - 2 = 1$ одиницю.

Інші учасники мають максимальний потенціал $0$. Отже, загальний потенціал за день $5$ дорівнює $1$.

У день $8$ є $8$ учасників із рівнями майстерності $[1, 2, 3, 1, 2, 3, 2, 3]$. Оптимальні зусилля дорівнюють $[2, 1, 0, 2, 1, 0, 1, 0]$, а відповідні максимальні потенціали — $[4, 2, 0, 2, 1, 0, 0, 0]$.