Height Problem in java

n people are standing in line numbered 1 to n from left to right. Each person wants to know the height of the person to left of him having height less than him. If there are multiple such people he wants to know the height of the person closest to him. If there is no such person report -1.

Input

line 1: contains an integer n denoting the size of array.

line 2: contains n separated integers denoting elements of array.

Output

The output should contain n space separated integers, the ith integer should be the height reported to ith person (-1 if no person to the left is found whose height is less).

Constraints

2 ≤ n ≤ 100000

0 ≤ arr[i] ≤ 1000000000

Time Complexity:O(n)

Sample Input

5
1 2 3 4 5

Sample Output

-1 1 2 3 4

Solution of Height Problem in java:–

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = input.nextInt();
        }
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++){
            while(stack.size() > 0 && stack.peek() >= a[i])
                stack.pop();
            if(stack.empty()){
                System.out.print(-1 + " ");
            }else{
                System.out.print(stack.peek() + " ");
            }
            stack.push(a[i]);
        }
    }
}