CF581B.Luxurious Houses

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

The capital of Berland has nn multifloor buildings. The architect who built up the capital was very creative, so all the houses were built in one row.

Let's enumerate all the houses from left to right, starting with one. A house is considered to be luxurious if the number of floors in it is strictly greater than in all the houses with larger numbers. In other words, a house is luxurious if the number of floors in it is strictly greater than in all the houses, which are located to the right from it. In this task it is assumed that the heights of floors in the houses are the same.

The new architect is interested in nn questions, ii -th of them is about the following: "how many floors should be added to the ii -th house to make it luxurious?" (for all ii from 11 to nn , inclusive). You need to help him cope with this task.

Note that all these questions are independent from each other — the answer to the question for house ii does not affect other answers (i.e., the floors to the houses are not actually added).

输入格式

The first line of the input contains a single number nn ( 1<=n<=1051<=n<=10^{5} ) — the number of houses in the capital of Berland.

The second line contains nn space-separated positive integers hih_{i} ( 1<=hi<=1091<=h_{i}<=10^{9} ), where hih_{i} equals the number of floors in the ii -th house.

输出格式

Print nn integers a1,a2,...,ana_{1},a_{2},...,a_{n} , where number aia_{i} is the number of floors that need to be added to the house number ii to make it luxurious. If the house is already luxurious and nothing needs to be added to it, then aia_{i} should be equal to zero.

All houses are numbered from left to right, starting from one.

输入输出样例

  • 输入#1

    5
    1 2 3 1 2
    

    输出#1

    3 2 0 2 0 
  • 输入#2

    4
    3 2 1 4
    

    输出#2

    2 3 4 0 
首页