SOLVE

LATER

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} \)

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