Question
Find Farthest Treasure Chest
You have a row of treasure chests, each holding a certain number of coins. For each chest at position i, you need to find the farthest chest to the right (position j) that contains at least as many coins as chest i. Your task is to determine this for every chest in the row.
Input
The first line of input contains a single integer N.
The second line of input contains N space-separated integers, denoting the elements of the array.
Constraints
1 ≤ N ≤ 105
1 ≤ A[i] ≤ 109
The second line of input contains N space-separated integers, denoting the elements of the array.
Constraints
1 ≤ N ≤ 105
1 ≤ A[i] ≤ 109
Output
Print N space-separated integers the values of j for each i from 1 to N.
Example
Sample Input
5
5 2 4 3 1
Sample Output
1 4 3 4 5
Explanation
Index 1: 5 is the largest element in the list, and no element in the right with equal value exist, thus the answer is the index itself.
Index 2: Index 3 (4) and 4 (3) have value greater than Index 2 (2), and index 4 is the farthest.
Index 3: No index in the right of index 3 with value greater than or equal to 4 exist, thus the answer is the index itself.
5
5 2 4 3 1
Sample Output
1 4 3 4 5
Explanation
Index 1: 5 is the largest element in the list, and no element in the right with equal value exist, thus the answer is the index itself.
Index 2: Index 3 (4) and 4 (3) have value greater than Index 2 (2), and index 4 is the farthest.
Index 3: No index in the right of index 3 with value greater than or equal to 4 exist, thus the answer is the index itself.