У магічному королівстві принцеса знайшла послідовність довжини $N$: $A = (A_1, A_2, A_3, ..., A_N)$. Для кожного підпослідовності $a = (A_1, A_2, A_3, ..., A_k)$ (де $1 \le k \le N$), принцеса хоче обчислити магічну суму $f(a)$, яка визначається наступним чином:

Для кожного $i = 1, 2, 3, ..., k$, у такому порядку, виконується наступна операція:

• Додати поточне максимальне значення елементу в $a$ до $a_i$.

Ваше завдання --- допомогти принцесі обчислити $f(a)$ для кожного $k$ від $1$ до $N$ (включно).

Input Specification

У першому рядку дається число $N$ --- довжина послідовності. ($1 \le N \le 2 \times 10^5$)

У другому рядку подається послідовність $A$ з $N$ елементів. ($1 \le A_i \le 10^7$)

Output Specification

Виведіть $N$ рядків. $k$-ий рядок має містити $f(a)$ для $a = (A_1, A_2, A_3, ..., A_k)$.

Sample Input 1

3
1 2 3

Sample Output 1

2
8
19