using System;

using System.Collections.Generic;

using System.Linq;

​

public class Program

{

    //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.

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

    //for example for 2 6 4 7 9 4 3 4

    //you should output -1 2 2 4 7 2 2 3

    public static void Main()

    {

        var n = new[] { 9, 3, 0, 1,5 };

        int[] result=FindNearesSmallest(n);

        Console.WriteLine("Orginal array :"+string.Join("",n));

        Console.WriteLine("Result array :"+string.Join("",result));

        int[] FindNearesSmallest(int[] input)

        {

            int n=input.Length;

            int[] result=new int[n];

           Stack<int> stack=new Stack<int>();

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

            while(stack.Count>0&& input[stack.Peek()]>=input[i]){

                stack.Pop();

            }

                result[i]=(stack.Count==0)?-1:input[stack.Peek()];

                stack.Push(i);

            }

            return result;

        }

    }

}