cf1237 D. Balanced Playlist

题意：

n首歌顺序播放，播完最后一首又会从头开始。每首歌有个值，听歌的过程中记住听过的最大值，如果遇到一首歌的值严格小于上述最大值的一半，马上停止听歌。问从每一首歌开始播放，分别能听几首歌

思路：

把环变成长度2倍的链，单调队列维护下降子列。

队头要怎么操作呢？如果 \(a_i\) 严格小于队头的一半，那就用 \(i\) 计算队头的答案。

这样一来，中间有一些位置没有答案。从右往左，它们的答案等于后一位置的答案+1

数组长度×2是为了正确找到最大值，但这题最多能听2n-1首歌，所以数组长度应该×3！

如果某个位置的答案大于2n-1，说明这个位置开始能无限听下去，按题目要求输出-1

const signed N = 3e5 + 3;
int n, a[N], ans[N];
int q[N], hh, tt = -1;

signed main() {
    iofast;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i], a[i+n] = a[i+n+n] = a[i];

    for(int i = 1; i <= 3*n; i++) {
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        while(hh <= tt && a[q[hh]] > 2*a[i]) ans[q[hh]] = i - q[hh], hh++; //上下俩while顺序无所谓
        q[++tt] = i;
    }

    for(int i = 3*n; i; i--) if(!ans[i]) ans[i] = ans[i+1] + 1;
    for(int i = 3*n; i; i--) if(ans[i] >= 2*n) ans[i] = -1;

    for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
}