beecrowd | 2851

Rangel's Challenge

By Diego Rangel, FACIT BR Brazil

Timelimit: 1

Rangel is a computer engineer who, in his spare time, loves to create fun games to entertain his friends.

One day, a teacher asked him to create a game that involved data structures so that the freshmen of his university would lose the fear of AEDs (Algorithms and Data Structures).

Due to the great difficulty of students with AEDs, Rangel created a game based on the indices of a array and gave the name "Rangel’s Challenge" (a very interesting game that can be played on any platform).

The Rangel’s Challenge game works as follows:

For example the array V = [1, 4, 7, 5], for a1 = 1 the answer will be 4 which is in position a2, since a2 > a1 and the index 2 > 1 and a2 is closest to a1, a2 = 4 the answer will be 7 which is in the position a3, since a3 > a2 and the index 3 > 2, already for a3 = 7 the answer will be “*” since there is no aj (j > 3 and j ≤ | V | which satisfies the conditions of the game, the same happens for a4 = 5. Thus the response to be typed in the console is the array M = [4, 7, *, *].

Rangel has no time to feed the database with the correct answers as he is preparing for a competition and asks you to create the answers for him, because the semester is almost starting and the teacher is waiting for the game.

Given array V, you must create an algorithm that generates the sequence M following the rules of the game.


The first line consists of single integer n (1 ≤ n ≤ 100000) which indicates the size of the array.

The next line contains n integers ai (1 ≤ in) which is the ith element of the array (1 ≤ ai ≤ 100).


Print n values ​​separated by a space following the problem's specifications, if there is no response for the ith element of V, print “*” without the quotation marks.

Input Samples Output Samples


1 4 7 5

4 7 * *


1 2

2 *