Closest Smaller Element on the Right

Given an array \(a_1, a_2, \dots, a_n\) of \(n\) integers, find for each element the closest smaller element which is to its right. In other words, for every index \(i\) (with \(1 \le i \le n\)), find the first index \(j\) such that \(i < j \le n\) and \(a_j < a_i\). If there is no such element, output \(-1\) for that position.

The problem can be solved using a stack to keep track of candidates, resulting in an efficient solution with linear complexity.

inputFormat

The first line contains a single integer \(n\) indicating the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single line containing \(n\) space-separated integers. Each integer is the closest smaller element to the right of the corresponding element in the array. If no such element exists, print \(-1\) for that position.

7
4 5 2 10 8 6 7

2 2 -1 8 6 -1 -1