Кто у кого может попытаться списать

Близится к завершению учебный год в Школе Нечародейства и Неволшебства, и сегодня ученики этой школы должны сдать экзамен по пройденному за весь год материалу.

Экзамен происходит в специальной комнате, где школьников рассаживают за длинный стол в один ряд. При этом расстояния между соседними местами за столом одинаковые. Учителя строго следят за тем, чтобы ученики писали экзаменационную работу самостоятельно. И чтобы пресечь возможность нарушения, преподавателям необходимо выяснить, у кого вероянее всего может попытаться списать тот или иной ученик.

Экзамен сдают N школьников. Они пронумерованы натуральными числами от 1 до N в том порядке, в котором они сидят за столом слева направо. Кроме того, для каждого ученика известен его уровень знаний – чем он выше, тем больше ученик знает.

Разумеется, школьнику имеет смысл списывать у кого-то из тех, кто имеет более высокий уровень знаний, чем у него самого, а удобнее всего списывать у того, кто сидит за столом ближе. Поэтому наиболее вероятным кандидатом, у которого будет списывать некоторый ученик, будет ближайший к нему из тех, кто имеет более высокий рейтинг. При этом, если несколько учеников, имеющих более высокий рейтинг, будут сидеть на одинаковом расстоянии от данного, то он отдаст предпочтение тому из них, кто сидит правее.

Помогите учителям определить, кто у кого может попытаться списать.

Входные данные
В первой строке задается натуральное число N – количество учеников, которые пришли на экзамен (1≤N≤2⋅10**5). Во второй строке записаны N целых чисел, i-е из которых определяет уровень знаний ученика с номером i. Все эти числа натуральные и не превосходят 10**9.

Выходные данные
Выведите N целых чисел, определяющих наиболее вероятных кандидатов для списывания: i-е число – это номер ученика, у которого будет списывать ученик, сидящий на i-м месте. Если для некоторого ученика не существует таких, у которых он мог бы попытаться списать, выведите его собственный номер на соответствующей позиции.

Миниатюры

 

0

Спасибо всем помощникам, не принявших участие в ответе. Муниципальный уровень олимпиады по состоянию на 13:30 мск окончен и работы более не принимаются. Теперь все желающие могут со спокойной душой могут помочь неучам и представить свои варианты решений.

З.Ы. Двоечникам отдельный привет.

0