Lexi, one of Santa's most trusted elf, has been tasked to shop for Christmas trees to design Santa's workshop!

His local Christmas tree vender arranges the trees in rows (which isn't the best way to arrange trees if you want to sell them). This causes Lexi to be only able to see one tree on either side of the row: the tallest one.

A tree is considered visible from one side of a row if its height is greater than all the other trees in front of it.

Given ~N~ trees arranged in a row, each tree with a height of ~h_i~, can you help Lexi figure out how much taller each tree has to be so that it can be visible from at least one side of the row?

Constraints

~1 \le N \le 10^6~

~1 \le h_i \le 10^6~

Input Specification

The first line contains one integer, ~N~.

The next line contains ~N~ space-seperated integers, the height of the ~i^{th}~ tree.

Output Specification

Output ~N~ lines, each containing one integer: the shortest length that needs to be added to the ~i^{th}~ tree so that it can be visible from at least one side.

Sample Input

5
1 5 2 3 4

Sample Output

0
0
3
2
0

Sample Output Explanation

The first tree is visible from the left since there are no trees in front of it from the left side.

The second tree is visible from the left since it is taller than the tree in front of it from the left side

The third tree is blocked from the left and right side, so you need to add an extention of height 3 to it to make it visible from the right side.

Similarly, the fourth tree needs to get an extention of height 2 to make it visible from the right side.

The fifth tree is visible from the right because there are no trees in front of it from the right side.