6.4 Magic Spells

Score: 60pts

Time Limit: 2.98 sec

Kiyomaru has an array A of size n. He has 2 magical spells known as “Zakeru” and “Zakerga” which he can perform on that array.

Zakeru is a powerful spell which he formally represents as F.

F(i) : Applying this spell on an index i such that 0 <= i <= n-1 returns the smallest index j such that i < j <= n-1 and A[i] < A[j]. It returns -1 if there is no such index.

Zakerga is another powerful spell represented as G.

G(i) : Applying this spell on index i such that 0 <= i <= n-1 returns the smallest index j such that i < j <= n-1 and A[i] > A[j]. It returns -1 if there is no such index.

Now kiyomaru combines the power of these spells into one and names it “Zaker”.

This spell is equal to casting Zakeru first and Zakerga afterwards.

Formally he represents Zaker as Z.

Z(i) : G(F(i))

Now he is curious to know the values of those indices that he gets after performing Zaker spell on each index.

Zakeru is a powerful spell which he formally represents as F.

F(i) : Applying this spell on an index i such that 0 <= i <= n-1 returns the smallest index j such that i < j <= n-1 and A[i] < A[j]. It returns -1 if there is no such index.

Zakerga is another powerful spell represented as G.

G(i) : Applying this spell on index i such that 0 <= i <= n-1 returns the smallest index j such that i < j <= n-1 and A[i] > A[j]. It returns -1 if there is no such index.

Now kiyomaru combines the power of these spells into one and names it “Zaker”.

This spell is equal to casting Zakeru first and Zakerga afterwards.

Formally he represents Zaker as Z.

Z(i) : G(F(i))

Now he is curious to know the values of those indices that he gets after performing Zaker spell on each index.

Constraints

1 <= n <= 30000

0 <= A[i] <= 10^18

0 <= A[i] <= 10^18

Input Format

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 line denotes .

Output Format

Print N space separated integers on a single line, where the integer denotes or -1, if does not exist.

Example 1

Input:

8

3

7

1

7

8

4

5

2

Output:

1 4 4 4 -1 2 -1 -1

Explanation:

Here is the result after he performs the magic spells on each index.

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

8

3

7

1

7

8

4

5

2

Output:

1 4 4 4 -1 2 -1 -1

Explanation:

Here is the result after he performs the magic spells on each index.

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