URI Online Judge | 2851

Desafio de Rangel

Por Diego Rangel, FACIT BR Brazil

Timelimit: 1

Rangel é um engenheiro da computação que, nas horas vagas, adora criar jogos divertidos para entreter os seus amigos.

Certo dia, um professor pediu que ele criasse um jogo que envolvesse estruturas de dados para que os calouros de sua universidade perdessem o medo de AEDs (Algoritmos e Estruturas de Dados).

Devido à grande dificuldade dos alunos com AEDs, Rangel criou um jogo baseado nos índices de um vetor e deu o nome de “Desafio de Rangel” (um jogo muito interessante e que pode ser jogado em qualquer plataforma).

O jogo Desafio de Rangel funciona da seguinte maneira:

Por exemplo o vetor V = [1, 4, 7, 5], para a1 = 1 a resposta será 4 que está na posição a2, pois a2 > a1 e o índice 2 > 1 e a2 é a o mais próximo do a1, para a2 = 4 a resposta será 7 que está na posição a3, pois a3 > a2 e o índice 3 > 2, já para a3 = 7 a resposta será “*” pois não existe um aj (j > 3 e j ≤ |V|) que satisfaça as condições do jogo o mesmo acontece para o a4 = 5. Logo a resposta a ser digita no console é o vetor M = [4, 7, *, *].

Rangel está sem tempo de alimentar o banco de dados com as respostas corretas, pois ele está se preparando para uma competição e pede a você que as crie as respostas para ele, pois o semestre está quase iniciando e o professor está esperando o jogo.

Dado o vetor V, você deve criar um algoritmo que gere a sequência M seguindo as regras do jogo.

Entrada

A primeira linha consiste de único inteiro n (1 ≤ n ≤ 100000) que indica o tamanho do vetor.

A próxima linha contém n inteiros ai (1 ≤ in) que é o i-ésimo elemento do vetor (1 ≤ ai ≤ 100).

Saída

Imprima n valores separados por um espaço seguindo as especificações do problema, caso não exista resposta para o i-ésimo elemento de V,  imprima “*” sem as aspas.

Exemplos de Entrada Exemplos de Saída

4

1 4 7 5

4 7 * *

2

1 2

2 *