思路：
假设从第i首歌开始听，结束位置为j，那么从第i+1首歌开始听，结束位置一定不早于j。可以用反证法证明。想到这一点，就不难解决了。
实现：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 const int N = 300005; 5 int a[N], st[N][20]; 6 int log2(int x) 7 { 8 int res = -1; 9 while (x) { x >>= 1; res++; } 10 return res; 11 } 12 void init(int n) 13 { 14 for (int i = 0; i < n; i++) st[i][0] = a[i]; 15 for (int j = 1; (1 << j) < n; j++) 16 { 17 for (int i = 0; i + (1 << j) - 1 < n; i++) 18 { 19 st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]); 20 } 21 } 22 } 23 int get_max(int l, int r) 24 { 25 if (l > r) return -INF; 26 int p = log2(r - l + 1); 27 return max(st[l][p], st[r - (1 << p) + 1][p]); 28 } 29 int main() 30 { 31 int n; 32 while (cin >> n) 33 { 34 int minn = INF, maxn = -INF; 35 for (int i = 0; i < n; i++) 36 { 37 cin >> a[i]; a[i + n] = a[i + 2 * n] = a[i]; 38 minn = min(a[i], minn); 39 maxn = max(a[i], maxn); 40 } 41 init(3 * n); 42 vector<int> res(n, -1); 43 if (maxn <= minn * 2) 44 { 45 for (auto it: res) cout << it << " "; 46 cout << endl; continue; 47 } 48 int cur = 0; 49 for (int i = 0; i < n; i++) 50 { 51 cur = max(cur, i + 1); 52 int maxn = get_max(i, cur); 53 while (cur < 3 * n && a[cur] * 2 >= maxn) 54 { 55 maxn = max(maxn, a[cur]); cur++; 56 } 57 res[i] = cur - i; 58 } 59 for (auto it: res) cout << it << " "; 60 cout << endl; 61 } 62 return 0; 63 }