There are N houses on a street, indexed from 1 to N. In the i^th house lives a person with socializing value A_i. On the i^th day, person living in the i^th house hosts a party at his house and invite all the people living in j^th house such that j < i and A_j > A_i. You have to print total distance traveled by all the people on the i^th day. Distance between house i and j is equal to |i - j|.

INPUT:
First line contains N.
Next line contains N space separated integers, i^th value denoting socializing value of the person living in the i^th house.

OUTPUT:
Print N space separated integers, i^th value denoting total distance traveled by all the people on the i^th day.

Constraints:
1 <= N <= 10⁵
1 <= A_i <= 10⁹