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 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 ≤ n ≤ 10^5), denoting the number of tracks in the playlist.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9), denoting coolnesses of the tracks.

Output

Output n integers c_1, c_2, …, 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 < (a_1)/(2). 
  * track 2: listen to track 2, stop as a_3 < (a_2)/(2). 
  * track 3: listen to track 3, listen to track 4, listen to track 1, stop as a_2 < (max(a_3, a_4, a_1))/(2). 
  * track 4: listen to track 4, listen to track 1, stop as a_2 < (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 < (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.
import java.io.*; 
import java.math.*;
import java.util.*;
 
public class Main {
	static final int MOD = 998244353;
	//static final long MOD = 1000000007;
	static boolean[] visited;
    public static void main(String[] args) throws IOException {
        FastScanner sc = new FastScanner();
        int N = sc.nextInt();
        int[] coolness = new int[2*N];
        for (int i = 0; i < 2*N; i++) {
        	if (i < N)
        		coolness[i] = sc.nextInt();
        	else
        		coolness[i] = coolness[i-N];
        }
        SegmentTreeRMQ tree = new SegmentTreeRMQ(2*N);
        tree.constructST(coolness);
        int[] ans = new int[2*N];
        for (int i = 0; i < N; i++) {
        	int low = i+1;
        	int high = i+N-1;
        	if (tree.RMQ(low, high) >= (coolness[i]+1)/2)
        		continue;
        	while (low < high) {
        		int mid = (low+high)/2;
        		if (tree.RMQ(low,mid) < (coolness[i]+1)/2) {
        			high = mid;
        		} else {
        			low = mid+1;
        		}
        	}
        	ans[i] = low-i;
        	ans[i+N] = ans[i];
        }
        //System.out.println(Arrays.toString(ans));
        int nonZero = -1;
        for (int i = 0; i < 2*N; i++) {
        	if (ans[i] > 0) {
        		nonZero = i;
        	}
        }
        
        if (nonZero >= 0) {
        	for (int i = nonZero-1; i >= 0; i--) {
        		if (ans[i] == 0)
        			ans[i] = ans[i+1]+1;
        		else
        			ans[i] = Math.min(ans[i],ans[i+1]+1);
        	}
        } else {
        	for (int i = 0; i < 2*N; i++)
        		ans[i]=-1;
        }
        
        StringBuilder print = new StringBuilder();
        for (int i = 0; i < N; i++)
        	print.append(ans[i] + " ");
        System.out.println(print);
    }
    
    static class SegmentTreeRMQ { 
        int st[]; //array to store segment tree
        int n;
        
        public SegmentTreeRMQ(int n) {
        	this.n = n;
        }
      
        // A utility function to get minimum of two numbers 
        int minVal(int x, int y) { 
            return (x < y) ? x : y; 
        } 
      
        // A utility function to get the middle index from corner 
        // indexes. 
        int getMid(int s, int e) { 
            return s + (e - s) / 2; 
        } 
      
        /*  A recursive function to get the minimum value in a given 
            range of array indexes. The following are parameters for 
            this function. 
      
            st    --> Pointer to segment tree 
            index --> Index of current node in the segment tree. Initially 
                       0 is passed as root is always at index 0 
            ss & se  --> Starting and ending indexes of the segment 
                         represented by current node, i.e., st[index] 
            qs & qe  --> Starting and ending indexes of query range */
        int RMQUtil(int ss, int se, int qs, int qe, int index) 
        { 
            // If segment of this node is a part of given range, then 
            // return the min of the segment 
            if (qs <= ss && qe >= se) 
                return st[index]; 
      
            // If segment of this node is outside the given range 
            if (se < qs || ss > qe) 
                return Integer.MAX_VALUE; 
      
            // If a part of this segment overlaps with the given range 
            int mid = getMid(ss, se); 
            return minVal(RMQUtil(ss, mid, qs, qe, 2 * index + 1), 
                    RMQUtil(mid + 1, se, qs, qe, 2 * index + 2)); 
        } 
      
        // Return minimum of elements in range from index qs (quey 
        // start) to qe (query end).  It mainly uses RMQUtil() 
        int RMQ(int qs, int qe) 
        { 
            // Check for erroneous input values 
            if (qs < 0 || qe > n - 1 || qs > qe) { 
                System.out.println("Invalid Input");
                return -1; 
            } 
      
            return RMQUtil(0, n - 1, qs, qe, 0); 
        } 
      
        // A recursive function that constructs Segment Tree for 
        // array[ss..se]. si is index of current node in segment tree st 
        int constructSTUtil(int arr[], int ss, int se, int si) 
        { 
            // If there is one element in array, store it in current 
            //  node of segment tree and return 
            if (ss == se) { 
                st[si] = arr[ss]; 
                return arr[ss]; 
            } 
      
            // If there are more than one elements, then recur for left and 
            // right subtrees and store the minimum of two values in this node 
            int mid = getMid(ss, se); 
            st[si] = minVal(constructSTUtil(arr, ss, mid, si * 2 + 1), 
                    constructSTUtil(arr, mid + 1, se, si * 2 + 2)); 
            return st[si]; 
        } 
      
        /* Function to construct segment tree from given array. This function 
           allocates memory for segment tree and calls constructSTUtil() to 
           fill the allocated memory */
        void constructST(int arr[]) 
        { 
            // Allocate memory for segment tree 
      
            //Height of segment tree 
            int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); 
      
            //Maximum size of segment tree 
            int max_size = 2 * (int) Math.pow(2, x) - 1; 
            st = new int[max_size]; // allocate memory 
      
            // Fill the allocated memory st 
            constructSTUtil(arr, 0, n - 1, 0);
        }
    }
    
    public static long power(long x, long y, long p) { 
        // Initialize result
        long res = 1;
         
        // Update x if it is more   
        // than or equal to p 
        x = x % p;  
      
        while (y > 0) 
        { 
            // If y is odd, multiply x 
            // with result 
            if((y & 1)==1) 
                res = (res * x) % p; 
      
            // y must be even now 
            // y = y / 2 
            y = y >> 1;  
            x = (x * x) % p;  
        } 
        return res; 
    }
    
    public static long dist(int[] point, int[] point2) {
    	return (long)(Math.pow((point2[1]-point[1]),2)+Math.pow((point2[0]-point[0]),2));
    }
    
    public static long gcd(long a, long b) {
    	if (b == 0)
    		return a;
    	else
    		return gcd(b,a%b);
    }
    
    public static int[][] sort(int[][] array) {
    	//Sort an array (immune to quicksort TLE)
		Random rgen = new Random();
		for (int i = 0; i < array.length; i++) {
		    int randomPosition = rgen.nextInt(array.length);
		    int[] temp = array[i];
		    array[i] = array[randomPosition];
		    array[randomPosition] = temp;
		}
		Arrays.sort(array, new Comparator<int[]>() {
			  @Override
        	  public int compare(int[] arr1, int[] arr2) {
				  if (arr1[1] != arr2[1])
					  return arr1[1]-arr2[1];
				  else if (arr1[2] != arr2[2])
					  return arr1[2]-arr2[2];
				  else
					  return arr1[3]-arr2[3];
	          }
		});
		return array;
	}
    
    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() { 
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str; 
        }
    }
}
class Node {
	public HashSet<Node> children;
	public int n;
	
	public Node(int n) {
		this.n = n;
		children = new HashSet<Node>();
	}
	
	public void addChild(Node node) {
		children.add(node);
	}
	
	public void removeChild(Node node) {
		children.remove(node);
	}

	/* (non-Javadoc)
	 * @see java.lang.Object#hashCode()
	 */
	@Override
	public int hashCode() {
		return n;
	}

	@Override
	public boolean equals(Object obj) {
		if (! (obj instanceof Node)) {
			return false;
		} else {
			Node node = (Node) obj;
			return (n == node.n);
		}
	}
}