Find the closest smaller value on the left

Given an array of n integers , you are asked to find the closest smaller value to the left of each element.

Input

The first line of the input contains a single integer n (1 ≀ n ≀ ).
The next line contains n space-separated integers ().

Output

The program should print n space-separated integers - the indices of the closest smaller value for each element in the given array. If such an element does not exist, the program should print 0.

Examples

Input
Output
8 4 7 2 5 10 5 4 7
0 1 0 3 4 3 3 7
Β 

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue