N,*H=`dd`.split.map &:to_i;
B=[0]*-~N;
U=->i,w{(B[i]=[B[i],w].max;i+=i&-i)while i<=N};
Q=->i{r=0;(r=[r,B[i]].max;i-=i&-i)while i>0;r};
A=H.pop N;
G=H.sort;
N.times{|i|
k=1+G.bsearch_index{|h|H[i]-h};
U[k,Q[k]+A[i]]
};
p Q[N]
