Balanced Playlist

2000ms

524288K

Description:

Your favorite music streaming platform has formed a perfectly balanced playlist exclusively for you. The playlist consists of $$$n$$$ tracks numbered from $$$1$$$ to $$$n$$$. The playlist is automatic and cyclic: whenever track $$$i$$$ finishes playing, track $$$i+1$$$ starts playing automatically; after track $$$n$$$ goes track $$$1$$$.

For each track $$$i$$$, you have estimated its coolness $$$a_i$$$. The higher $$$a_i$$$ is, the cooler track $$$i$$$ is.

Every morning, you choose a track. The playlist then starts playing from this track in its usual cyclic fashion. At any moment, you remember the maximum coolness $$$x$$$ of already played tracks. Once you hear that a track with coolness strictly less than $$$\frac{x}{2}$$$ (no rounding) starts playing, you turn off the music immediately to keep yourself in a good mood.

For each track $$$i$$$, find out how many tracks you will listen to before turning off the music if you start your morning with track $$$i$$$, or determine that you will never turn the music off. Note that if you listen to the same track several times, every time must be counted.

Input:

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$), denoting the number of tracks in the playlist.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), denoting coolnesses of the tracks.

Output:

Output $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$, where $$$c_i$$$ is either the number of tracks you will listen to if you start listening from track $$$i$$$ or $$$-1$$$ if you will be listening to music indefinitely.

Sample Input:

4
11 5 2 7

Sample Output:

1 1 3 2

Sample Input:

4
3 2 5 3

Sample Output:

5 4 3 6

Sample Input:

3
4 3 6

Sample Output:

-1 -1 -1

Note:

In the first example, here is what will happen if you start with...

track $$$1$$$: listen to track $$$1$$$, stop as $$$a_2 < \frac{a_1}{2}$$$.
track $$$2$$$: listen to track $$$2$$$, stop as $$$a_3 < \frac{a_2}{2}$$$.
track $$$3$$$: listen to track $$$3$$$, listen to track $$$4$$$, listen to track $$$1$$$, stop as $$$a_2 < \frac{\max(a_3, a_4, a_1)}{2}$$$.
track $$$4$$$: listen to track $$$4$$$, listen to track $$$1$$$, stop as $$$a_2 < \frac{\max(a_4, a_1)}{2}$$$.

In the second example, if you start with track $$$4$$$, you will listen to track $$$4$$$, listen to track $$$1$$$, listen to track $$$2$$$, listen to track $$$3$$$, listen to track $$$4$$$ again, listen to track $$$1$$$ again, and stop as $$$a_2 < \frac{max(a_4, a_1, a_2, a_3, a_4, a_1)}{2}$$$. Note that both track $$$1$$$ and track $$$4$$$ are counted twice towards the result.

Informação

Provedor Codeforces

Código CF1237D