12 months ago

suryansh jaiswal • 370

Lucknow

Solution

void solve()
{
int n;
cin>>n;
int ar[n];
f(i,n)
cin>>ar[i];
vector<int> pref(n);
pref[0]=ar[0];
vector<pair<int,int>> v;
v.pb({ar[0],1});
for(int i=1;i<n;i++)
{
    pref[i]=pref[i-1]+ar[i];
    v.pb({pref[i],i+1});
}
sor(pref);
sort(v.begin(),v.end());
vector<int> mn(n);
mn[n-1]=v[n-1].second;
for(int i=n-2;i>=0;i--)
mn[i]=min(mn[i+1],v[i].second);
//cout<<pref<<endl;
//cout<<mn<<endl;
int q;
cin>>q;
f(i,q)
{
    int x;
    cin>>x;
    auto it=lower_bound(pref.begin(),pref.end(),x);
    if(it==pref.end())
    {
        cout<<-1<<" ";
        continue;
    }
    int pos=lower_bound(pref.begin(),pref.end(),x)-pref.begin();
    cout<<mn[pos]<<" ";
}
cout<<endl;

}