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