Danh sách phát cân bằng

Một danh sách phát gồm $n$ bài hát được đánh số từ $1$ đến $n$. Danh sách phát theo vòng lặp: ngay sau khi bài $i$ kết thúc thì bài $i+1$ bắt đầu phát; sau bài $n$ là bài $1$.

Mỗi bài $i$ có độ "hay" $a_i$. Bạn chọn một bài để bắt đầu, danh sách sẽ phát từ bài đó theo thứ tự vòng tròn. Tại mọi thời điểm, gọi $x$ là độ "hay" lớn nhất trong tất cả các bài đã phát từ lúc bắt đầu. Ngay khi gặp một bài có độ hay nhỏ hơn ngặt $x/2$ (không làm tròn), bạn lập tức tắt nhạc.

Với mỗi bài $i$, hãy tính số bài bạn sẽ nghe nếu bắt đầu từ bài $i$, hoặc xác định bạn sẽ nghe nhạc mãi mãi. Nếu bạn nghe cùng một bài nhiều lần, mỗi lần đều được đếm.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ ($2\le n\le {10}^5$) — số bài trong danh sách.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^9$).

Dữ liệu ra

In ra $n$ số $c_1,c_2,\dots ,c_n$, trong đó $c_i$ là số bài bạn nghe khi bắt đầu từ bài $i$, hoặc $-1$ nếu bạn không bao giờ tắt nhạc.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le a_i\le {10}^9$

Ví dụ