#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
typedef long long ll;
int n,m,a[N],b[N];
ll sa[N],sb[N];
bool check(int l,int r,int d){
	ll mx=-1e18;
	for(int i=l;i<=r;++i){
		mx=max(mx,sa[i-1]+sb[i-1]-1ll*d*i);
		if(1ll*d*(i+1)-sb[i+1]-sa[i]+mx>0)return false;
	}
	return true;
}
vector<int> testset(vector<int> A, vector<int> B, vector<int> L, vector<int> U){
	n=A.size(),m=L.size();
	for(int i=1;i<=n;++i)a[i]=A[i-1];
	for(int i=2;i<=n;++i)b[i]=B[i-2];
	for(int i=1;i<=n+1;++i)sa[i]=sa[i-1]+a[i],sb[i]=sb[i-1]+b[i];
	vector<int>ans(m);
	for(int i=0;i<m;++i){
		int l=0,r=2e8;
		while(l<r){
			int mid=l+r+1>>1;
			if(check(L[i]+1,U[i]+1,mid))l=mid;
			else r=mid-1;
		}
		ans[i]=l;
	}
	return ans;
}
/*
int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%d%d",&n,&m);
	vector<int>A(n),B(n-1),L(m),U(m);
	for(int i=0;i<n;++i)scanf("%d",&A[i]);
	for(int i=0;i<n-1;++i)scanf("%d",&B[i]);
	for(int i=0;i<m;++i)scanf("%d%d",&L[i],&U[i]);
	vector<int>ans=testset(A,B,L,U);
	for(int i=0;i<m;++i)printf("%d\n",ans[i]);
	return 0;
}*/