#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n, q; long long A[N], S[N];

namespace SegmentTree {
#define lc (u << 1)
#define rc (u << 1 | 1)
    vector<long long> C[N << 2];
    inline vector<long long> merge(vector<long long> A, vector<long long> B) {
        vector<long long> C = A;
        for(auto x : B) { C.emplace_back(x);
            while(C.size() >= 3 && C[C.size() - 3] <= C[C.size() - 2] && C[C.size() - 1] <= C[C.size() - 2]) {
                long long y = C[C.size() - 3] + C[C.size() - 1] - C[C.size() - 2]; C.pop_back(), C.pop_back(), C.pop_back();
                C.emplace_back(y);
            }
        }
        return C;
    }
    inline void Build(int u, int l, int r) {
        if(l != r) {
            int mid = (l + r) >> 1;
            Build(lc, l, mid), Build(rc, mid + 1, r);
            C[u] = merge(C[lc], C[rc]);
        } else C[u].emplace_back(A[l]);
    }
    vector<long long> Ask(int u, int l, int r, int L, int R) {
        if(l >= L && r <= R) return C[u];
        int mid = (l + r) >> 1;
        if(mid >= R) return Ask(lc, l, mid, L, R);
        if(mid < L) return Ask(rc, mid + 1, r, L, R);
        return merge(Ask(lc, l, mid, L, R), Ask(rc, mid + 1, r, L, R));
    }
#undef lc
#undef rc
}

inline void solve(vector<long long> &A, int L, int R) {
    long long res = 0; int flag = 1;
    int l = 0, r = A.size() - 1;
    while(l <= r) {
        if(A[l] >= A[r]) res += flag * A[l ++], flag *= -1;
        else res += flag * A[r --], flag *= -1;
    }
    cout << (S[R] - S[L - 1] + res) / 2 << ' ' << (S[R] - S[L - 1] - res) / 2 << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i ++) cin >> A[i];
    for(int i = 1; i <= n; i ++) S[i] = S[i - 1] + A[i];
    SegmentTree::Build(1, 1, n);

    while(q --) {
        int l, r; cin >> l >> r;
        auto vec = SegmentTree::Ask(1, 1, n, l, r);
        solve(vec, l, r);
    }

    return 0;
}