Destroy The Village

Time limit: 0.5s Memory limit: 64MB Input: Output:

A village is being raided by a barbarian, who, despite being on his own, shouldn't be underestimated.

The village consists of NN houses, numbered from 00 to N1N-1 and arranged in a straight line perpendicular to the shore, with house ii being DiD_i meters away from the shore.

The barbarian's strategy is simple: he will raze the house he is in, then move to the closest house that hasn't been razed yet, until all the treasures in the village have been hoarded.
If there is more than one house at the minimum distance, the barbarian will move to the one closest to the shore first.

The villagers have a plan though, which is to hide in the last house that the barbarian will raid to face him when he's most tired.
Trying to predict the barbarian's moves is giving them an headache, moreover, the raid may start from any house.
In order to help them, you have to find, for each possible starting house ii, which house HiH_i would be destroyed last by the barbarian.

Input data

The input file consists of:

  • a line containing integer NN.
  • a line containing the NN integers D0,,DN1D_{0}, \, \ldots, \, D_{N-1}.

Output data

The output file must contain a single line consisting of the NN integers H0,,HN1H_{0}, \, \ldots, \, H_{N-1}.

Constraints and clarifications

  • 2N1062 \le N \le 10^6.
  • 0Di10120 \le D_i \le 10^{12} for each i=0N1i=0\ldots N-1.
  • Di>Di1D_i > D_{i-1} for each 1iN11 \le i \le N-1.
  • For tests worth 1212 points, N100N \le 100, Di109D_i \le 10^9, for each 0iN10 \le i \le N-1.
  • For tests worth 2828 more points, N1000N \le 1000.
  • For tests worth 3535 more points, N100000N \le 100\,000.

Example

stdin

5
1 4 6 7 10

stdout

4 0 4 4 0 

Explanation

  • When the barbarian starts from house 00, located 11 meter away from the shore, he destroys it, then moves to house 11, at a distance of 33 meters from house 00, then to house 22, then 33. The last house standing is number 44.
  • When the barbarian starts from house 11, located 44 meter away from the shore, he destroys it, then moves to house 22, at a distance of 22 meters from house 11, then to house 33, then 44. The last house standing is number 00.
  • When the barbarian starts from house 22, located 66 meter away from the shore, he destroys it, then moves to house 33, at a distance of 11 meter from house 22, then to house 11. Note that both house 11 and 44 are at a distance of 33 meters from house 33, but house 11 is closer to the shore. He then moves to house 00. The last house standing is number 44.
  • When the barbarian starts from house 33, located 77 meter away from the shore, he destroys it, then moves to house 22, at a distance of 11 meter from house 33, then to house 11, then 00. The last house standing is number 44.
  • When the barbarian starts from house 44, located 1010 meter away from the shore, he destroys it, then moves to house 33, at a distance of 33 meters from house 44, then to house 22, then 11. The last house standing is number 00.

Log in or sign up to be able to send submissions!