Indices of Next Smaller Element
Given an array of N integers, for each element a[i], find the index j such that j > i, a[j] < a[i], and j is minimized. If no such element exists, use -1. Print these indices for all elements from left to right.
Input
The first line contains an integer N, the size of the array. The second line contains N space-separated integers representing the array elements.
Output
Print N space-separated integers, where the i-th integer is the index of the next smaller element to the right for a[i], or -1 if none exists. Indices are 0-based.
Constraints
1 <= N <= 200000 1 <= a[i] <= 10^9
Example 1
5 2 1 5 6 2
1 -1 4 4 -1
For 2 (idx 0), next smaller is 1 (idx 1). For 1 (idx 1), none. For 5 (idx 2), next smaller is 2 (idx 4). For 6 (idx 3), next smaller is 2 (idx 4). For 2 (idx 4), none.
Example 2
7 5 4 3 2 1 6 7
1 2 3 4 -1 -1 -1
All elements from index 0 to 4 have a strictly smaller element to their right. Elements at indices 5 and 6 do not.
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 1 5 6 2
7 5 4 3 2 1 6 7