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

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Assembly, C#, C++, D, Dart, Go, Groovy, Java, Javascript, Kotlin, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Ruby, Rust, Scratch, Typescript, Zig

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 \leq n \leq 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 \leq a_{i} \leq 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 \leq n \leq 10^{5}$
$1 \leq a_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 11 5 2 7	1 1 3 2	Bắt đầu từ bài 3: nghe các bài 3, 4, 1 (độ hay lớn nhất tới đó là $11$ ), rồi gặp bài 2 có $a_{2} = 5 < 11 / 2$ nên dừng — đã nghe $3$ bài.
4 3 2 5 3	5 4 3 6	Bắt đầu từ bài 4: nghe các bài 4, 1, 2, 3, 4, 1 (độ hay lớn nhất là $5$ ), rồi gặp bài 2 có $a_{2} = 2 < 5 / 2$ nên dừng — đã nghe $6$ bài. Bài 1 và bài 4 đều được đếm hai lần.
3 4 3 6	-1 -1 -1	Bắt đầu từ bất kỳ bài nào, độ hay lớn nhất sẽ đạt $6$ , và không có bài nào nhỏ hơn $6 / 2 = 3$ nên không bao giờ dừng.

Bình luận

Không có bình luận tại thời điểm này.