A Game of Numbers

 Problem:-

You are given an array A of N integers. Now, two functions $F(X)$ and $G(X)$ are defined:

$F(X)$ : This is the smallest number Z such that $X<Z\le N$ and $A[X]<A[Z]$

$G(X)$ : This is the smallest number Z such that $X<Z\le N$ and $A[X]>A[Z]$

Now, you need to find for each index i of this array $G(F(i))$, where $1\le i\le N$ . If such a number does not exist, for a particular index i, output 1 as its answer. If such a number does exist, output $A[G(F(i))]$

Input :

The first line contains a single integer N denoting the size of array A. Each of the next N lines contains a single integer, where the integer on the $i^{th}$ line denotes $A[i]$.

Output :

Print N space separated integers on a single line, where the $i^{th}$ integer denotes $A[G(F(i))]$ or 1, if $G(F(i))$ does not exist.

Constraints:

$1\le N\le 30000$

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

Sample Input

8
3
7
1
7
8
4
5
2

Sample Output

1 4 4 4 -1 2 -1 -1

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Next Greater     Next Smaller
3 --> 7                 7 -->1
7 --> 8                 8 -->4
1 --> 7                 7 --> 4
7 --> 8                 8 --> 4
8 --> -1                -1 --> -1
4 --> 5                 5 --> 2
5 --> -1                -1 --> -1
2 --> -1                -1 --> -1

Code:-

#include<stdio.h>

int main()

{

int n,i,flag=0,j,k;

long long int a[30000];

scanf("%d",&n);

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

{

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

}

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

{

flag=0;

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

{

if(a[i]<a[j])

break;

}

if(j==n){

printf("-1 ");

flag=1;

}

else{

for(k=j;k<n;k++)

if(a[j]>a[k])

break;

}

if(k==n&&flag==0)

printf("-1 ");

else

if(flag==0)

printf("%lld ",a[k]);

}

return 0;

}