#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int maxn = 200005;

int n,Q;
int a[maxn],sum[maxn];

vector<int>merge(vector<int>V1,vector<int>V2)
{
	vector<int>R(V1);
	int rn=R.size();
	
	for(auto c:V2)
	{
		R.push_back(c);
		rn++;
		
		while(rn>=3 && R[rn-2]>=R[rn-1] && R[rn-2]>=R[rn-3])
		{
			R[rn-3]= R[rn-3]+R[rn-1]-R[rn-2];
			rn-=2;
			R.pop_back();
			R.pop_back();
		}
	}
	return R;
}
int getans(vector<int>V)
{
	int ret=0;
	int l=0,r=V.size()-1;
	while(l<=r)
	{
		if(V[l]>=V[r]) ret+=V[l],l++;
		else ret+=V[r],r--;
		
		if(l<=r)
		{
			if(V[l]>=V[r]) ret-=V[l],l++;
			else ret-=V[r],r--;
		}
	}
	return ret;
}
struct segment
{
	vector<int>seg[maxn<<2];
	void build(const int x,const int l,const int r)
	{
		if(l==r)
		{
			seg[x].push_back(a[l]);
			return;
		}
		int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
		build(lc,l,mid); build(rc,mid+1,r);
		seg[x]=merge(seg[lc],seg[rc]);
	}
	int lx,rx;
	vector<int> query(const int x,const int l,const int r)
	{
		if(rx<l||r<lx) return {};
		if(lx<=l&&r<=rx) return seg[x];
		int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
		return merge(query(lc,l,mid),query(rc,mid+1,r));
	}
}seg;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>Q;
	for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
	
	seg.build(1,1,n);
	
	while(Q--)
	{
		int l,r;
		cin>>l>>r;
		
		seg.lx=l,seg.rx=r;
		vector<int>V= seg.query(1,1,n);

		
		int kk=getans(V),kc=sum[r]-sum[l-1];
		cout<< (kc+kk)/2<<' '<<(kc-kk)/2 <<'\n';
	}
	
	return 0;	
}