【題目敘述】https://codeforces.com/contest/1237/problem/D
【解題想法】Monotonic Queue (單調隊列)
- 讀入測資後,先複製兩份,接在原資料後方(總共三份)。
- 下圖例說明,有時候會跨越到第三份資料才夠找出最長的播放清單。

- 維護一個嚴格遞減的單調隊列,存放資料的index。
- 維護條件:
- dq.front() <= 2 * a[i]:否則,從dq前端開始pop,最後一個不滿足條件的index (now)及其前方尚未得到答案的所有index (j),都可以一併計算出答案 (i – j)。
- dq.back() >= a[i]:否則,從dq後端開始pop,直到條件成立。
- dq.push_back(i)

#include <iostream>
#include <deque>
using namespace std;
const int maxn = 1e5+5;
int n, a[maxn*3], mn = 1e9+5, mx = 0, ans[maxn], now, l;
deque <int> dq;
int main() {
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
a[i+n] = a[i];
a[i+n*2] = a[i];
mn = min(mn, a[i]);
mx = max(mx, a[i]);
}
if (mx <= mn*2){
for (int i = 0; i < n; i++){
if (i != 0) cout << " ";
cout << -1;
}
cout << "\n";
}else{
dq.push_back(0);
l = 0;
for (int i = 1; i < n*3; i++){
if (!dq.empty() && a[dq.front()] > a[i]*2){
while (!dq.empty() && a[dq.front()] > a[i]*2){
now = dq.front();
dq.pop_front();
}
for (int j = l; j <= now; j++){
ans[j] = i - j;
}
l = now+1;
}
while (!dq.empty() && a[dq.back()] < a[i]){
dq.pop_back();
}
dq.push_back(i);
}
for (int i = 0; i < n; i++){
cout << ans[i] << " ";
}
cout << "\n";
}
}