Beautiful Houses

Interview

Time limit1sMemory limit1024 MB

Summary

For each house, find how many floors it must gain to be taller than every house with a larger number, or 0 if it already is.

Level: Easy3 of 10
Topics: Array
Solved: No attempts yet

Problem

In a certain city somewhere in Lithuania there is a very unusual street. The architect who planned it was so inventive that all houses stand on only one side of the street. The houses are numbered 1 to $N$ . A house farther from the start of the street has a larger number than a house closer to it. All houses look nearly identical, and only their heights differ.

As on any street, the residents want their homes to be beautiful. They agreed that a house is beautiful if it is taller than every house with a larger number.

Each resident wants to know whether their house is beautiful, and if not, how many floors it lacks to become beautiful.

Compute the shortfall for each house separately.

Note: residents who learn how many floors their houses lack will not build extra floors, so the shortfall of each house must be computed separately.

Input

The first line contains the number of houses $N$ . The second line contains $N$ integers $a_i$ , the height of the house numbered $i$ .

Output

Print $N$ integers $p_i$ , the number of floors the house numbered $i$ lacks to become beautiful. If a house is already beautiful, print $0$ for it.

Constraints

$1 \le N, a_i \le 100\,000$

Examples2

Example 1
Input
```
5
3 3 2 1 2
```
Expected output
```
1 0 1 2 0
```
Example 2
Input
```
4
2 3 1 2
```
Expected output
```
2 0 2 0
```