1784C - Monsters (hard version) - CodeForces Solution

///The imagination can believe anything so we must lead not follow it
///we are not our thoughts
///Don't ask for permission, ask for forgiveness
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 500500
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
const ll M=1e9+7;

ll a[N],ans[N];

main()
{
    fast;

    ll i=0,j,k,n,m,idx,x,y,z;

    int tt=1;
    cin>>tt;
    while(tt--)
    {
        cin>>n;
        vector<pair<ll,ll>>b;
        for(i=0;i<n;i++)
        {
            cin>>a[i];
            b.pb({a[i],i});
        }
        ll l=0;
        ll mx=-1,cnt=0;
        sort(b.begin(),b.end());
        set<ll>st;
        for(i=0;i<n;i++)
        {
            //cout<<b[i].first<<" "<<b[i].second<<endl;

            st.insert(b[i].second);
            auto it=st.end();
            it--;
            mx=*it;
            if(l+1>b[i].first)
            {
                ans[mx]-=b[i].first;
                //ans[mx]+=mx+1;
                //cout<<mx<<ans[mx]<<endl;
                st.erase(it);
                cnt++;
            }
            else
            {
                l++;
            }
        }
        j=2;
        cnt=0;
        ans[0]+=a[0]-1;
        for(i=1;i<n;i++)
        {
            if(ans[i]!=0)
            {

            }
            else
            {
                ans[i]-=j;
                j++;
            }
            ans[i]+=ans[i-1];
            ans[i]+=a[i];
        }
        for(i=0;i<n;i++)
        {
            cout<<ans[i]<<" ";
        }
        cout<<endl;
        for(i=0;i<n;i++)
        {
            ans[i]=0;
        }


























    }
    return 0;

}
/*
1
27
23 23 21 18 10 13 24 4 26 14 9 16 1 8 9 2 20 26 13 1 16 10 19 1 16 22 26



22 43 61 75 80 87 104 100 117 121 119 123 111 105 99 85 88 96 90 90 86 75 72 72 65 63 64
*/