On one side of a perpendicular horizontal wall nails n nails, numbered from 1 to N, the coordinates of the ith nail is (i,hi). Mr.After want to do an interesting experiment, he puts a vertical infinite light bar in each nail, and then gently pushes it to the right, light rod lean backward to right down under the action of gravity, until a full 180 degree rotation, in the whole process, the bottom of light bar and the nail sub are always connected together.

Now Mr.After would like to know, for each nail on the experiment, whether the light rod will finally encounter another nail. If it will, then output the smallest id of nails encountered, otherwise output 0.

For each test case

The first line contains a positive integer n, indicating the number of nails (n<=1000000)

The second line gives the N number, the ith number indicates hi (1<=hi<=1000000)

For each test case

Output a line contains n integers, indicating the answer to each experiment