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.


-----Examples-----
Input
4
11 5 2 7

Output
1 1 3 2

Input
4
3 2 5 3

Output
5 4 3 6

Input
3
4 3 6

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.

Difficulty: interview

Starter code:

Solutions:
#TO MAKE THE PROGRAM FAST

''' ----------------------------------------------------------------------------------------------------  '''
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
from collections import deque
''' ----------------------------------------------------------------------------------------------------  '''




#FOR TAKING INPUTS

''' ----------------------------------------------------------------------------------------------------  '''
def li():return [int(i) for i in input().rstrip('\n').split(' ')]
def val():return int(input().rstrip('\n'))
def st():return input().rstrip('\n')
def sttoli():return [int(i) for i in input().rstrip('\n')]
''' ----------------------------------------------------------------------------------------------------  '''




#MAIN PROGRAM

''' ----------------------------------------------------------------------------------------------------  '''

d = deque()
n = val()
l = li()
j = x = 0
currmax = -10000000000000
ans = []
for i in range(n):
    while len(d) and d[0] < i:d.popleft()
    currmax = l[d[0]%n] if len(d) else l[i]
    while j<3*n:
        currmax = max(currmax,l[j%n])
        while len(d) and l[d[-1]%n] <= l[j%n]:d.pop()
        d.append(j)
        if currmax/2 > l[j%n]:
            ans.append(j-i)
            break
        j += 1
    if j == 3*n:
        print(*([-1 for _______ in range(n)]))
        return
print(*ans)





''' ----------------------------------------------------------------------------------------------------  '''

NN = 18
MI = [1<<100] * ((1<<NN+1)-1)
 
def update(x):
    i = (1<<NN) - 1 + x
    MI[i] = x
    while True:
        i = (i-1) // 2
        MI[i] = min(MI[2*i+1], MI[2*i+2])
        if i == 0:
            break

def rangemin(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    mi = 1<<100
    while l < r:
        if l%2:
            mi = min(mi, MI[l-1])
            l += 1
        if r%2:
            r -= 1
            mi = min(mi, MI[r-1])
        l >>= 1
        r >>= 1
    return mi

N = int(input())
A = [int(a) for a in input().split()]
B = sorted([(A[i], i) for i in range(N)])
i = 0 # large
j = 0 # small
X = [1<<20] * (2*N)
while i < N:
    while 2 * B[j][0] < B[i][0]:
        update(B[j][1])
        update(B[j][1]+N)
        j += 1
    X[B[i][1]] = rangemin(B[i][1], B[i][1]+N)
    X[B[i][1]+N] = X[B[i][1]] + N
    i += 1
for i in range(2*N-1)[::-1]:
    X[i] = min(X[i], X[i+1])
for i in range(N):
    X[i] -= i
X = [a if a < (1<<20) else -1 for a in X[:N]]
print(*X)


import sys
input = sys.stdin.readline

n=int(input())
A=list(map(int,input().split()))

B=[(-a,i) for i,a in enumerate(A)]

from collections import deque

LIST=deque()
LIST.append(B[0])

for b,i in B[1:]:
    if b>LIST[-1][0]:
        LIST.append((b,i))

import bisect

DIS=[-1]*n

for i in range(n-1,-1,-1):
    x=bisect.bisect(LIST,(-A[i]//2,1<<20))
    if x<len(LIST):
        DIS[i]=LIST[x][1]

    while len(LIST)>=1 and A[i]<=-LIST[0][0]:
        LIST.popleft()

    LIST.appendleft(B[i])

if max(DIS)==-1:
    print(*[-1]*n)
    return

for i in range(n):
    if DIS[i]!=-1:
        start=i
        break

ANS=[-1]*n

if DIS[start]>start:
    ANS[start]=DIS[start]-start
else:
    ANS[start]=DIS[start]+(n-start)


for i in range(start-1,-1,-1):
    if DIS[i]==-1:
        ANS[i]=ANS[(i+1)%n]+1
    else:
        if DIS[i]>i:
            ANS[i]=min(DIS[i]-i,ANS[(i+1)%n]+1)
        else:
            ANS[i]=min(DIS[i]+(n-i),ANS[(i+1)%n]+1)

for i in range(n-1,-1,-1):
    if DIS[i]==-1:
        ANS[i]=ANS[(i+1)%n]+1
    else:
        if DIS[i]>i:
            ANS[i]=min(DIS[i]-i,ANS[(i+1)%n]+1)
        else:
            ANS[i]=min(DIS[i]+(n-i),ANS[(i+1)%n]+1)

for i in range(n-1,-1,-1):
    if DIS[i]==-1:
        ANS[i]=ANS[(i+1)%n]+1
    else:
        if DIS[i]>i:
            ANS[i]=min(DIS[i]-i,ANS[(i+1)%n]+1)
        else:
            ANS[i]=min(DIS[i]+(n-i),ANS[(i+1)%n]+1)
    

print(*ANS)
        


import sys
readline = sys.stdin.readline

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx - self.N0

N = int(readline())
A = list(map(int, readline().split()))
B = [2*a for a in A]
B *= 3
inf = 2*10**9
B.append(-2)
T = Segtree(B, inf, True, min)

NN = T.N0

J = [0]*(NN+1)
J[3*N] = inf
KK = [None]*(NN+1)
for i in range(3*N-1, -1, -1):
    a = A[i%N]
    k = T.binsearch(i, NN, lambda x: x < a ,reverse = False)
    KK[i] = k
    J[i] = min(J[i+1], k)

Ans = [-1]*N
for i in range(N):
    j = J[i]
    if j == 3*N:
        continue
    Ans[i] = j - i
print(*Ans)

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class Binary_Indexed_Tree():
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i):
        return self.sum_range(i, i)

    def sum(self, i):
        ret = 0
        while i:
            ret += self.data[i]
            i &= i-1
        return ret

    def sum_range(self, l, r):
        return self.sum(r)-self.sum(l-1)

    def lower_bound(self, w):
        if w<=0:
            return 0
        i = 0
        k = 1<<(self.n.bit_length())
        while k:
            if i+k <= self.n and self.data[i+k] < w:
                w -= self.data[i+k]
                i += k
            k >>= 1
        return i+1

class RangeMinimumQuery:
    def __init__(self, n, func=min, inf=float("inf")):
        self.n0 = 2**(n-1).bit_length()
        self.op = func
        self.inf = inf
        self.data = [self.inf]*(2*self.n0)

    def construct(self, lis):
        for i, x in enumerate(lis):
            self.data[i+self.n0-1] = x
        for i in range(self.n0-2, -1, -1):
            self.data[i] = self.op(self.data[2*i+1], self.data[2*i+2])

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = self.inf
        while l < r:
            if r&1:
                r -= 1
                res = self.op(res, self.data[r-1])
            if l&1:
                res = self.op(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

n = int(input())
a = list(map(int, input().split()))
a = [i*2 for i in a]
BIT = Binary_Indexed_Tree(2*n)
RMQ = RangeMinimumQuery(2*n)
RMQ.construct(a+a)

b = [[j,i] for i,j in enumerate(a)]
b.sort(reverse=True)
ans = [0]*n
for j, i in b:
    cnt = BIT.sum(2*n-i)
    tmp = float("inf")
    if cnt:
        p = 2*n-BIT.lower_bound(cnt)
        tmp = p-i + ans[p%n]
    BIT.add(2*n-i, 1)
    BIT.add(n-i, 1)
    left = i
    right = 2*n
    if RMQ.query(i, right) < j//2:
        while right-left>1:
            mid = (right+left)//2
            if RMQ.query(i, mid) < j//2:
                right = mid
            else:
                left = mid
        tmp = min(tmp, right-i-1)
    ans[i] = tmp
ans = [i if i!=float("inf") else -1 for i in ans]
print(*ans)


import sys
input = sys.stdin.readline

class SegTree(object):
	"""docstring for SegTree"""
	def __init__(self, n, arr):
		self.n = n
		self.arr = arr
		self.tree = [0 for i in range(2*n)]

	def construct(self): # Construction
		for i in range(self.n):
			self.tree[n+i] = self.arr[i]
		for i in range(n-1,0,-1):
			self.tree[i] = self.function(self.tree[2*i],self.tree[2*i+1])

	def update(self,index,change):
		start = index+self.n
		self.tree[start] = value
		while start>0:
			self.tree[start] = self.function(self.tree[2*start],self.tree[2*start+1])
			start = start//2

	def calc(self,low,high): # 0-indexed
		low+=self.n
		high+=self.n
		ans = 0 # Needs to initialised
		while low<high:
			if low%2:
				ans = self.function(ans, self.tree[low])
				low += 1
			if high%2:
				high -= 1
				ans = self.function(ans, self.tree[high])
			low = low//2
			high = high//2
		return ans
	
	def function(self,a,b): # Function used to construct Segment Tree
		return max(a,b)

n = int(input())*3
a = list(map(int,input().split()))
a = a + a + a
st = SegTree(n,a)
st.construct()
ans = [-1]*n
m = a[0]
flag = 0
for i in range(1,n):
	if a[i]<=(m-1)//2:
		ans[0] = i
		flag = 1
		prev = i
		break
	else:
		m = max(m,a[i])
if not flag:
	print(*ans[0:n//3])
	return
for i in range(1,n//3):
	if a[i]>=a[i-1]:
		ans[i] = ans[i-1]-1
	else:
		maxx = st.calc(i,prev+1)
		while a[prev]>(maxx-1)//2:
			# print (prev,i,maxx)
			maxx = max(maxx,a[prev])
			prev += 1
		ans[i] = prev - i
print(*ans[0:n//3])