craft=lambda:map(int,input().split()) n,m=craft() *an,=craft() by=[[0],[0]] for x in by: for u,v in zip([0]+an,an):x+=x[-1]+max(0,u-v), an=an[::-1] by[1]=[0]+by[1][::-1] for _ in[0]*m:s,t=craft();l=by[s>t];print(abs(l[s]-l[t]))
?