H. Слабое звено
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии по воскресеньям проходит известое шоу — игра «Слабое звено».

В игре принимают участие $$$n$$$ игроков, которые выстраиваются в круг. Каждому игроку сопоставлен рейтинг — некоторое целое число $$$a_i$$$.

Игра проходит в несколько раундов, каждый из которых выглядит следующим образом:

  • В очередном раунде принимают участие все ещё не выбывшие игроки.
  • Все игроки, которые по рейтингу строго слабее обоих своих соседей по кругу, объявляются слабым звеном и выбывают из игры.
  • Все оставшиеся участники сдвигаются чуть плотнее, чтобы снова образовывать круг.
  • Игра заканчивается, если после очередного раунда осталось ровно два человека или если после очередного раунда не выбыл ни один человек.
  • Иначе начинается новый раунд.

Можно показать, что если до очередного раунда в игре оставалось хотя бы три участника, то после одного раунда гарантированно останется не менее двух участников.

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

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

В первой строке дано одно целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество участников в игре.

Вторая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 200\,000$$$) — рейтинги всех участников игры в том порядке, в котором они стоят, при этом участник с номером $$$n$$$ является соседом участника с номером $$$1$$$.

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

Выведите $$$n$$$ целых чисел — номер раунда, в котором участник игры с номером $$$i$$$ покинет игру, или $$$0$$$, если этот игрок останется до конца игры.

Раунды нумеруются последовательными целыми числами начиная с $$$1$$$.

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

В первом примере игра проходит следующим образом (при помощи _ обозначаются выбывшие участники):

$$$[4; 5; 5; 2; 3] \to [4; 5; 5; \_; 3] \to [4; 5; 5; \_; \_] \to [\_; 5; 5; \_; \_]$$$

После этого игра заканчивается, так как осталось ровно два человека.

Во втором примере игра проходит следующим образом:

$$$[5; 1; 3; 1; 5] \to [5; \_; 3; \_; 5] \to [5; \_; \_; \_; 5]$$$

В третьем и чётвертом примере нет ни одного игрока, который был бы одновременно слабее обоих своих соседей, поэтому игра заканчивается, не успев начаться.