A Game of Numbers

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}$

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

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;