← 返回题目列表

Codeforces · 1237/D

D. 平衡的播放列表

中文机器翻译题面 查看原题

您最喜欢的音乐流媒体平台已经为您专门制作了一个完美平衡的播放列表。播放列表由 $$$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$$$(如果您将无限期地听音乐)。

示例

输入 #1

4
11 5 2 7

输出 #1

1 1 3 2

输入 #2

4
3 2 5 3

输出 #2

5 4 3 6

输入 #3

3
4 3 6

输出 #3

-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$$$ 都在结果中计算两次。