Statement

A village is being raided by a barbarian, who, despite being on his own, shouldn't be underestimated. The village consists of N houses, numbered from 0 to N-1 and arranged in a straight line perpendicular to the shore, with house i being D_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 i, which house H_i would be destroyed last by the barbarian.