A Game of Numbers
Tag(s):

## Data Structures, Easy, Stack

Problem
Editorial
Analytics

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

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Sapient Global Markets Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting