Print Previous Smaller Element
EasyPractice library · +10 XPstack
Given a sequence of N integers, for each integer in the sequence, find the closest integer to its left that is strictly smaller than it. If no such integer exists, report -1. Print these results for each integer in the original sequence.
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 previous smaller element for a_i, or -1 if none exists.
Constraints
1 <= N <= 1000 -10^9 <= a_i <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
5 2 5 1 4 3
Output
-1 2 -1 1 1
For 2, no previous smaller element (-1). For 5, 2 is smaller. For 1, no previous smaller (-1). For 4, 1 is smaller. For 3, 1 is smaller.
Example 2
Input
4 1 2 3 4
Output
-1 1 2 3
Each element's previous smaller element is the one immediately to its left.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 2 5 1 4 3
Example 2 input
4 1 2 3 4