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.

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 $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.