E. Выбор морковки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

В ряд расположены n морковок. Морковка на позиции i слева имеет сочность ai. Олег думает, что ZS любит сочные морковки, а Игорь считает, что он ненавидит сочные морковки. Поэтому Олег хочет максимизировать сочность морковки, которую они выберут, а Игорь хочет минимизировать сочность морковки, которою они выберут.

Чтобы не разругаться, они опять решили сыграть в игру. Олег и Игорь будут ходить по очереди, первым будет ходить Олег. На каждом ходу игрок может взять одну морковку с любого конца ряда и съесть ее. Игра закончится, как только останется одна морковка. Она и будет той морковкой, которую они дадут своему другу ZS.

Олег — подловатый клиент. Пока Игорь отошел, Олег хочет выполнить k ходов до начала игры. Каждый из этих ходов будет таким же, как и в обычной игре (т.е. съесть одну морковку с любого из концов ряда). Когда Игорь вернется, они начнут игру как обычно, Олег все равно будет ходить первым.

Олегу стало интересно: для всех k таких, что 0 ≤ k ≤ n - 1, какова сочность морковки, которую они подарят ZS, если он сделает k ходов заранее, и оба игрока действуют оптимально?

Входные данные

В первой строке содержится одно целое число n (1 ≤ n ≤ 3·105) — количество морковок в ряду.

Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109). Число ai обозначает сочность i-й морковки слева.

Выходные данные

Выведите n целых чисел x0, x1, ..., xn - 1. Число xi должно быть сочностью морковки, которые друзья подарят ZS, если k = i.

Примеры
Входные данные
4
1 2 3 5
Выходные данные
3 3 5 5
Входные данные
5
1000000000 1000000000 1000000000 1000000000 1
Выходные данные
1000000000 1000000000 1000000000 1000000000 1000000000
Примечание

Рассмотрим первый пример.

Если k = 0, то одна из оптимальных игр выглядит так:

  • Олег съедает морковку с сочностью 1.
  • Игорь съедает морковку с сочностью 5.
  • Олег съедает морковку с сочностью 2.
  • Остается морковка с сочностью 3.

Если k = 1, то одна из оптимальных игр выглядит так:

  • Олег съедает морковку с сочностью 1 заранее.
  • Олег съедает морковку с сочностью 2.
  • Игорь съедает морковку с сочностью 5.
  • Остается морковка с сочностью 3.

Если k = 2, то одна из оптимальных игр выглядит так:

  • Олег съедает морковку с сочностью 1 заранее.
  • Олег съедает морковку с сочностью 2 заранее.
  • Олег съедает морковку с сочностью 3.
  • Остается морковка с сочностью 5.

Если k = 3, то одна из оптимальных игр выглядит так:

  • Олег съедает морковку с сочностью 1 заранее.
  • Олег съедает морковку с сочностью 2 заранее.
  • Олег съедает морковку с сочностью 3 заранее.
  • Остается морковка с сочностью 5.

Таким образом, ответ равен 3, 3, 5, 5.

Во втором примере Олег всегда может съесть морковку с сочностью 1, так как он ходит первым. Поэтому сочность оставшейся морковки всегда равна 1000000000.