Nearest Smaller Values

Given an array of integers, for each element, find the nearest element to its left that is strictly smaller. If there is no such element, output -1 for that position.

For an element a_i at index i (0-indexed), you need to find the maximum index j such that j < i and a_j < a_i. If no such j exists, output -1 for that element.

Formally, for each element a_i, compute:

\[ result[i] = \begin{cases} a_j & \text{if } j = \max \{ k \mid k < i \text{ and } a_k < a_i \} \\ -1 & \text{if no such } k \text{ exists} \end{cases} \]

The input is given via standard input and the output should be printed to standard output. The first line of input contains an integer n representing the number of elements, followed by a line of n space-separated integers.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), 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 where the i-th integer is the nearest smaller value to the left of ai. If there is none, print -1 for that position.

6
2 5 3 7 8 1

-1 2 2 3 7 -1