Nearest Smaller Element

 Problem:-

Given an array, find the nearest smaller element G[i] for every element A[i] in the array such that the element has an index smaller than i.

More formally,

G[i] for an element A[i] is an element A[j] such that 
    j is maximum possible AND 
    j < i AND
    A[j] < A[i]

Elements for which no smaller element exist, consider next smaller element as -1.

Input Format

First line contains an integer N denoting the number of elements in the array (not necessarily distinct).

Second line contains N space separated integers denoting the elements of the array.

Output Format

Print N space separated integers denoting the array G.

Constraints

 $1\le N\le {10}^5$

$0\le A[i]\le {10}^6$

Sample Input

8
39 27 11 4 24 32 32 1

Sample Output

-1 -1 -1 -1 4 24 24 -1

Time Limit: 2

Memory Limit: 256

Source Limit:

Code:-

#include<stdio.h>

long int stack[100000],top=-1;

int main()

{

long int a[100000],i,n;

    scanf("%ld",&n);

    for(i=0;i<n;i++)

     scanf("%ld",&a[i]);

    top++;

    stack[top]=n-1;

    for(i=n-2;i>=0;i--)

    {

        if(a[i]>=a[stack[top]])

        {

            top++;

            stack[top]=i;

        }

        else

        {

            while(top!=-1 && a[i]<a[stack[top]])

            {

                a[stack[top]]=a[i];

                top--;

            }

            top++;

            stack[top]=i;

        }

    }

    while(top!=-1)

    {

        a[stack[top]]=-1;

        top--;

    }

    for(i=0;i<n;i++)

     printf("%ld ",a[i]);

    return 0;

}