Задача №113941. Слабое звено
В Берляндии по воскресеньям проходит известое шоу — игра «Слабое звено».
В игре принимают участие \(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\).
В первом примере игра проходит следующим образом (при помощи _ обозначаются выбывшие участники):
\([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]\)
В третьем и чётвертом примере нет ни одного игрока, который был бы одновременно слабее обоих своих соседей, поэтому игра заканчивается, не успев начаться.
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