# 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 denoting the number of elements in the array (not necessarily distinct).

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

Output Format

Print space separated integers denoting the array G.

Constraints

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

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

Sample Input
`839 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]=n1;
for(i=n2;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;
}