While reading the statement of this problem, we recommend forgetting that summer consists of $$$92$$$ days and that a day consists of $$$1440$$$ minutes. This is Berland, and things are different here.

Monocarp is a student at a provincial university in Berland. The summer holidays have just begun, and they will last for the next $$$n$$$ days. Monocarp has long dreamed of going to the capital of Berland, so he will choose one day $$$i$$$ among these days, arrive in the capital on that day, and spend the rest of the holidays there.

The capital of Berland is not a very cheap city, and Monocarp has $$$0$$$ Berland dollars with him. Naturally, this is not enough to visit interesting places and buy souvenirs. Therefore, on some days in the capital, Monocarp will work as a freelancer. He does not want to work in his hometown, since he has already spent the whole academic year doing university assignments.

Formally, on the $$$i$$$-th day of the holidays, Monocarp will have $$$a_i$$$ free minutes, which he will spend either working or resting and buying souvenirs. If Monocarp has at least $$$a_i$$$ dollars at the beginning of the $$$i$$$-th day, then on that day he will spend them on rest and souvenirs at a rate of $$$1$$$ dollar per minute; that is, during this day, he will spend $$$a_i$$$ dollars. Otherwise, he will spend this time working, earning $$$1$$$ dollar per minute; that is, during this day, he will earn $$$a_i$$$ dollars. Note that Monocarp always makes his decision for the entire day; it is impossible for him to both spend and earn money during the same day.

Your task is to determine, for each number of days $$$k$$$ from $$$1$$$ to $$$n$$$, how many dollars Monocarp will have left after the last day of the holidays if he lives in the capital for exactly $$$k$$$ last days (i. e. if he arrives on the day $$$(n-k+1)$$$).

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 10^{5}$$$).

The second line contains $$$n$$$ integers $$$a_{i}$$$ ($$$1 \le a_{i} \le n$$$).

Output

Print $$$n$$$ integers, where the $$$k$$$-th integer must be equal to the number of dollars Monocarp will have left if he lives in the capital for exactly $$$k$$$ last days (i. e. if he arrives on the day $$$(n-k+1)$$$).

Summer Vacation

Examples