Zenyk-businessman

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk knows better than anyone that the easiest way to earn a lot in IT is to found your own outsource company.

Since Zenyk is very good at selling dubious opportunities, he already has \(n\) candidates, and the \(i\)-th of them has already been offered a salary of \(a_i\). Moreover, Zenyk has already managed to find a large client — the company “Abetka”, which doesn’t count money, but cares very much about equality inside Zenyk’s company. Therefore, contrary to common sense, “Abetka” ignores the money spent and wants to minimize the inequality — the difference between the highest and lowest paid employees.

Of course, deep down Zenyk understands that such a policy will probably lead “Abetka” to bankruptcy, but he decided to exploit this vulnerability. Since Zenyk’s company, like a true outsource company, takes a certain percentage of the employees’ salary for itself, it makes no sense for Zenyk to decrease the candidates’ salaries. Therefore, to satisfy the client, he will change the offered salaries in the following way — an arbitrary number of times he will choose some candidate and double his salary (moreover, he can choose the same candidate an arbitrary number of times).

However, the main question remains unresolved — exactly how many employees does Zenyk need to hire? Therefore, for each number \(i\) from \(1\) to \(n\), he asks you to find out the minimum inequality that can be obtained if the first \(i\) candidates in the list are employed.

Input

The first line is given a natural number \(n\) — the number of candidates for Zenyk’s company.

The second line is given \(n\) natural numbers — the initial salaries for each of these candidates.

Output

Print \(n\) numbers separated by a space — what minimum salary inequalities Zenyk can achieve by hiring the first \(i\) candidates.

Constraints

\(1 \le n \le 10^5\),

\(1 \le a_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 4 7 3 33	0 1 2 9

Notes

Let’s consider the example.

If Zenyk hires only the first person, then no matter how much he pays them, the inequality will be \(0\).

If Zenyk hires people with salaries \(4\) and \(7\), it is optimal to double the salary of the first and get an inequality of \(1\).

If Zenyk hires people with salaries \(4\), \(7\) and \(3\), it is optimal to double the salary of the first and the third and get an inequality of \(2\).

If Zenyk decides to hire all people, it is optimal to triple the salary of the first and the third, double it for the second, and leave the salary of the fourth candidate unchanged. Thus, the final salaries will be \(32, 28, 24, 33\), and the inequality will be \(33 - 24 = 9\).