Беговой клуб набирает участников и быстро растёт: каждый день к нему присоединяется ровно один новый участник. Каждый участник приходит с определённым начальным уровнем мастерства и получает уникальный идентификатор в порядке своего прихода.

В конце каждого дня Тренер любит вычислять показатель, который он называет «общим потенциалом» клуба. Это значение представляет собой просто сумму индивидуальных потенциалов всех текущих участников. Чтобы поддерживать мотивацию участников, потенциал каждого из них рассчитывается с помощью гипотетического сценария «что, если», включающего одну интенсивную тренировку.

В этой воображаемой тренировке участник может приложить некоторое количество усилий, чтобы временно повысить свой уровень мастерства. За каждую $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]$.