Find Closest Smaller Element
Given an array of N integers, for each element, find the index of the closest element to its left that is strictly smaller than it. If no such element exists, report -1. If there are multiple such elements at the same minimum distance, report the one with the smallest index.
Input
The first line contains an integer N. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print N space-separated integers, where the i-th integer is the index (1-based) of the closest element to the left of A_i that is strictly smaller than A_i, or -1 if no such element exists.
Constraints
1 <= N <= 200000 1 <= A_i <= 10^9
Example 1
5 2 5 1 4 3
-1 1 -1 3 3
For 2, no smaller element to the left (-1). For 5, 2 is smaller and closest (index 1). For 1, no smaller element (index -1). For 4, 1 is smaller and closest (index 3). For 3, 1 is smaller and closest (index 3).
Example 2
3 10 20 5
-1 1 -1
For 10, -1. For 20, 10 is smaller (index 1). For 5, no smaller element (index -1).
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 2 5 1 4 3
3 10 20 5