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

Ваша любимая музыкальная платформа сформировала идеально сбалансированный плейлист специально для вас. В плейлисте $$$n$$$ треков, пронумерованные от $$$1$$$ до $$$n$$$. Плейлист автоматический и циклический: когда трек $$$i$$$ заканчивает воспроизведение, сразу включается трек $$$i+1$$$; за треком $$$n$$$ идёт трек $$$1$$$.

Для каждого трека $$$i$$$ вы оценили его крутость $$$a_i$$$. Чем больше $$$a_i$$$, тем круче трек $$$i$$$.

Каждое утро вы выбираете трек. Плейлист начинает играть с этого трека в последовательном циклическом порядке. В любой момент вы помните крутость $$$x$$$ самого крутого из уже сыгранных треков. Как только вы слышите, что начинает играть трек с крутостью строго меньше $$$\frac{x}{2}$$$ (без округления), вы сразу же выключаете музыку, чтобы не портить себе хорошее настроение.

Для каждого трека $$$i$$$ найдите, сколько треков вы послушаете перед тем, как выключите музыку, если начнёте утро с трека $$$i$$$, или же определите, что вы никогда не выключите музыку. Обратите внимание, что если вы послушаете один трек несколько раз, все эти разы нужно посчитать.

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

Первая строка содержит целое число $$$n$$$ ($$$2 \le n \le 10^5$$$) — число треков в плейлисте.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — крутости треков.

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

Выведите $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$, где $$$c_i$$$ — либо число треков, которые вы послушаете, если начнёте слушать с трека $$$i$$$, либо $$$-1$$$, если вы будете слушать музыку бесконечно.

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

Вот что произойдёт в первом примере, если вы начнёте слушать с...

  • трека $$$1$$$: послушаете трек $$$1$$$, остановитесь, так как $$$a_2 < \frac{a_1}{2}$$$.
  • трека $$$2$$$: послушаете трек $$$2$$$, остановитесь, так как $$$a_3 < \frac{a_2}{2}$$$.
  • трека $$$3$$$: послушаете трек $$$3$$$, послушаете трек $$$4$$$, послушаете трек $$$1$$$, остановитесь, так как $$$a_2 < \frac{\max(a_3, a_4, a_1)}{2}$$$.
  • трека $$$4$$$: послушаете трек $$$4$$$, послушаете трек $$$1$$$, остановитесь, так как $$$a_2 < \frac{\max(a_4, a_1)}{2}$$$.

Во втором примере, если вы начнёте с трека $$$4$$$, вы послушаете трек $$$4$$$, послушаете трек $$$1$$$, послушаете трек $$$2$$$, послушаете трек $$$3$$$, послушаете снова трек $$$4$$$, послушаете снова трек $$$1$$$ и остановитесь, так как $$$a_2 < \frac{max(a_4, a_1, a_2, a_3, a_4, a_1)}{2}$$$. Обратите внимание, что трек $$$1$$$ и трек $$$4$$$ учтены в результате дважды.