# Educational Codeforces Round 162 D. Slimes

蛤要我寫的，但我覺得沒必要，因為這場我只有寫出梗題 :cold_sweat:

### 題序:有$n$ $(1\le\ n\le\ 3\cdot 10^5)$ 隻史萊姆，大小分別為$a_i$ $(1\le\ a_i\le\ 10^9)$，每一秒會有一隻史萊姆吃掉他兩側大小嚴格小於他的史萊姆 (吃掉之後等同與兩隻合併了) 求每一隻史萊姆最短能活多少秒

#### 可以發現每次吃完就是加上你吃的值，而假設一開始從第 $a_i$ 隻沿著同方向吃到第 $a_{i+k}$ 隻，則我們總共吃了 $\sum_{j=i}^{k} size[j]$。
#### 這是同方向的，但要是不是同方向就燒雞了，要是你左右端點都不能吃旁邊的，你就判爛了 :cold_sweat:

#### 而這時候就會需要觀察到一個性質，假設你選擇一個區間，則只要他可以吃，他就可以吃到底，也就是把整個區間吃完，且不影響這個區間和剩下地方的相對位置。

#### 證明:
#### 要是有一個區間有可以吃的地方，且他不能吃完，則代表他會有一段或以上可以吃的，且每段之間會有一個以上整段加起來都不能超過的值，叫他 $maxsize$，而這個時候我們觀察這些點的邊緣(也就是和可以相加的段相連的點)，可以發現這些點是可以吃他其中一邊的數的，首先他一定有一邊的數都一定不會超過他，再來要是相等的話，因為前面有提到旁邊的區間是可以加的，而加了之後也不會超過 $maxsize$，所以也矛盾，得證。

#### 接下來就發現可以二分搜區間和外加特判能不能吃，然後再走一些路(?我覺得其實偏不走路) 就沒了

##### 不會講話所以直接上扣

The middle of adventure, such a perfect place to start
⣿⣿⣿⣿⣿⣿⣿⢿⠟⢿⣿⣿⣿⣿⠿⠛⠛⠿⢿⣿⣿⣿⣿⠛⣿⢿⣿⣿⣿⣿
⣿⣿⣿⡿⢿⣿⣿⣄⠄⣼⣿⡿⠋⠄⠄⠄⠄⠄⠄⠄⠛⣿⣿⠄⢀⣤⣿⣿⣿⣿
⣿⣿⣷⣤⣸⣿⠛⡛⢛⣿⠋⠄⠄⢀⠄⠄⠄⠄⠄⠄⠄⠘⣿⣿⡿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⡿⠁⠄⠁⠈⠄⠄⠄⠄⣿⡀⠄⠄⠄⠄⠄⠄⠄⠓⠸⠏⠄⢹⣿⣿⣿
⣿⣿⣿⡿⠄⠄⠄⠄⠄⠄⠄⢠⠿⠿⢻⣦⣤⣠⠄⠄⠄⠄⠄⠄⠄⠄⠈⠻⣿⣿
⣿⣿⡿⠁⠄⠄⠄⠄⠈⠄⠄⢸⣿⣿⣿⣿⣿⢭⡛⡀⠄⠄⠨⠄⠄⠄⠄⠄⣿⣿
⣿⣿⠁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠻⣧⡀⣈⣿⣿⠟⠄⠄⠠⢇⠄⠄⠄⠄⠄⣿⣿
⣿⡁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⢀⣉⡉⠉⠄⠄⠄⠄⠄⠰⠂⠄⠄⠄⠄⢹⣿
⣿⡇⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⣿⠿⠁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠘⣿
⣿⣿⣶⣤⣤⣄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⣼⣿
*/
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;

void solve(){
int n;
cin>>n;
vector<ll> pref(n+1),repeat(n+1),ans(n+1,INF);
rep(i,1,n+1)cin>>pref[i];
rep(i,1,n+1)repeat[i]+=repeat[i-1]+(pref[i]!=pref[i-1]);
rep(i,1,n+1)pref[i]+=pref[i-1];
rep(i,1,n+1){
ll l1=i+1,l2=0,r1=n+1,r2=i-1;
for(ll mid;l1<r1;){
mid=l1+r1>>1;
if(pref[mid]-pref[i]>pref[i]-pref[i-1]&&(repeat[mid]-repeat[i+1]||mid==i+1))r1=mid;
else l1=mid+1;
}
if(l1!=n+1)ans[i]=min(ans[i],l1-i);
for(ll mid;l2<r2;){
mid=l2+r2+1>>1;
if(pref[i-1]-pref[mid-1]>pref[i]-pref[i-1]&&(repeat[i-1]-repeat[mid]||mid==i-1))l2=mid;
else r2=mid-1;
}
if(i<n&&pref[i+1]-pref[i]>pref[i]-pref[i-1])ans[i]=1;
if(i>1&&pref[i-1]-pref[i-2]>pref[i]-pref[i-1])ans[i]=1;
if(!l2&&l1==n+1&&ans[i]==INF)ans[i]=-1;
else if(l2)ans[i]=min(ans[i],i-l2);
}
rep(i,1,n+1)cout<<ans[i]<<' ';
cout<<'\n';
}

int main(){
IOS
int t;
cin>>t;
for(;t--;)solve();
}