#include<bits/stdc++.h>
#define reg register
#define int long long
inline int min(reg int x,reg int y){return x<y?x:y;}
inline bool cmin(reg int &x,reg int y){return x>y?x=y,1:0;}
const int N=5e5+10,INF=1e18;
int n,m,a[N],b[N],idx,rt[N],lim[N];
struct Line{
	int k,b;
	inline int operator()(const int &A)const{return k*A+b;}
	inline Line operator+(const Line &A)const{return {k+A.k,b+A.b};}
}tmp,tmp2;
struct Node{Line pre,suf,sum,mn; int t;}tr[N<<2];
int ls[N<<5],rs[N<<5];
inline int upd(reg Line &A,reg Line B,reg int x){
	if (A(x)>B(x)) std::swap(A,B);
	return A.k<=B.k?INF:(B(x)-A(x))/(A.k-B.k)+x+1; 
}
inline Node merge(reg Node A,reg Node B,reg int x){
	reg Node C={A.pre,B.suf,A.sum+B.sum,A.mn,min(A.t,B.t)};
	cmin(C.t,upd(C.suf,B.sum+A.suf,x)),cmin(C.t,upd(C.pre,A.sum+B.pre,x));
	cmin(C.t,upd(C.mn,B.mn,x)),cmin(C.t,upd(C.mn,A.suf+B.pre,x));
	return C;
}
void build(reg int &o,reg int l,reg int r){
	o=++idx; if (l==r) return tmp={-1,a[l]+b[l]},tmp2={-1,a[l]+b[l]+b[l-1]},tr[o]={tmp,tmp2,tmp,tmp2,INF},void();
	reg int mid=l+r>>1; build(ls[o],l,mid),build(rs[o],mid+1,r),tr[o]=merge(tr[ls[o]],tr[rs[o]],0);
}
void modify(reg int &o,reg int pre,reg int l,reg int r,reg int x){
	tr[o=++idx]=tr[pre],ls[o]=ls[pre],rs[o]=rs[pre]; if (l==r) return; reg int mid=l+r>>1;
	if (tr[ls[o]].t==x) modify(ls[o],ls[pre],l,mid,x); if (tr[rs[o]].t==x) modify(rs[o],rs[pre],l,mid,x); 
	tr[o]=merge(tr[ls[o]],tr[rs[o]],x);
}
Node query(reg int o,reg int l,reg int r,reg int L,reg int R,reg int x){
	if (L<=l&&r<=R) return tr[o]; reg int mid=l+r>>1;
	if (R<=mid) return query(ls[o],l,mid,L,R,x); if (L>mid) return query(rs[o],mid+1,r,L,R,x);
	return merge(query(ls[o],l,mid,L,R,x),query(rs[o],mid+1,r,L,R,x),x);
}
#undef int
std::vector<int> testset(std::vector<int> A, std::vector<int> B, std::vector<int> L, std::vector<int> U){
	std::vector<int> res;
	#define int long long
	n=A.size(); for (reg int i=1;i<=n;i++) a[i]=A[i-1],i<n?b[i]=B[i-1]:0;
	build(rt[m=1],1,n),lim[m]=0;
	while (1){
		if (tr[rt[m]].t>1000000000) break;
		lim[m+1]=tr[rt[m]].t,modify(rt[m+1],rt[m],1,n,lim[m+1]),m++;
	}
	// for (reg int i=1;i<=m;i++) std::cerr<<lim[i]<<" "; std::cerr<<"\n";
	// assert(0);
	for (reg int i=0;i<L.size();i++){
		// std::cerr<<"<< "<<i<<"\n";
		reg int l=1,r=m,now,pl=L[i]+1,pr=U[i]+1;
		while (l<=r){
			reg int mid=l+r>>1;
			if (query(rt[mid],1,n,pl,pr,lim[mid]).mn(lim[mid])>=0) l=mid+1,now=mid; else r=mid-1;
		}
		// std::cerr<<"qwq\n";
		reg int ans; l=lim[now],r=lim[now+1]-1;
		while (l<=r){
			reg int mid=l+r>>1;
			if (query(rt[now],1,n,pl,pr,mid).mn(mid)>=0) l=mid+1,ans=mid; else r=mid-1;
		}
		res.push_back(ans);
	}
	return res;
}