#include <iostream>
#include <deque>
#include <math.h>
#include <cmath>
#include <algorithm>

#define int int64_t

using namespace std;
const int N = 1e5;

typedef deque <int> di;

class SegmentTree
{
    public:
        int n;
        int32_t tree [4 * N + 1] = {};
        void tree_build(di a, int v, int l, int r)
        {
            if (l == r)
            {
                tree [v] = a [l];
                return;
            }
            int mid = (l + r) / 2;
            tree_build(a, v * 2, l, mid);
            tree_build(a, v * 2 + 1, mid + 1, r);
            tree [v] = tree [v * 2] + tree [v * 2 + 1];
        }
        void tree_build(int a [], int v, int l, int r)
        {
            if (l == r)
            {
                tree[v] = a[l];
                return;
            }
            int mid = (l + r) / 2;
            tree_build (a, v * 2, l, mid);
            tree_build (a, v * 2 + 1, mid + 1, r);
            tree [v] = tree [v * 2] + tree [v * 2 + 1];
        }
        void tree_update(int v, int l, int r, int where, int what)
        {
            if (l == r)
            {
                tree [v] = what;
                return;
            }
            int mid = (l + r) / 2;
            if (mid >= where)
                tree_update(v * 2, l, mid, where, what);
            else
                tree_update(v * 2 + 1, mid + 1, r, where, what);
            tree [v] = tree [v * 2] + tree [v * 2 + 1];
        }
        int tree_request(int v, int l, int r, int rl, int rr)
        {
            if (rl > rr)
                return 0;
            if (l == rl && r == rr)
                return tree [v];
            int mid = (l + r) / 2;
            return tree_request(v * 2, l, mid, rl, min(mid, rr)) + tree_request(v * 2 + 1, mid + 1, r, max(mid + 1, rl), rr);
        }
};

class SegmentTreemx
{
    public:
        int n;
        int32_t tree [4 * N + 1] = {};
        void tree_build(di a, int v, int l, int r)
        {
            if (l == r)
            {
                tree [v] = a [l];
                return;
            }
            int mid = (l + r) / 2;
            tree_build(a, v * 2, l, mid);
            tree_build(a, v * 2 + 1, mid + 1, r);
            tree [v] = max(tree [v * 2], tree [v * 2 + 1]);
        }
        void tree_build(int a [], int v, int l, int r)
        {
            if (l == r)
            {
                tree[v] = a[l];
                return;
            }
            int mid = (l + r) / 2;
            tree_build (a, v * 2, l, mid);
            tree_build (a, v * 2 + 1, mid + 1, r);
            tree [v] = max(tree [v * 2], tree [v * 2 + 1]);
        }
        void tree_update(int v, int l, int r, int where, int what)
        {
            if (l == r)
            {
                tree [v] = what;
                return;
            }
            int mid = (l + r) / 2;
            if (mid >= where)
                tree_update(v * 2, l, mid, where, what);
            else
                tree_update(v * 2 + 1, mid + 1, r, where, what);
            tree [v] = max(tree [v * 2], tree [v * 2 + 1]);
        }
        int tree_request(int v, int l, int r, int rl, int rr)
        {
            if (rl > rr)
                return 0;
            if (l == rl && r == rr)
                return tree [v];
            int mid = (l + r) / 2;
            return max(tree_request(v * 2, l, mid, rl, min(mid, rr)), tree_request(v * 2 + 1, mid + 1, r, max(mid + 1, rl), rr));
        }
};

int32_t main() {
    int n;
    cin >> n;
    int a [n];
    for (auto &i: a)
        cin >> i;
    SegmentTree sum;
    SegmentTreemx mx;
    sum.tree_build(a, 1, 0, n - 1);
    mx.tree_build(a, 1, 0, n - 1);
    int q;
    cin >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << sum.tree_request(1, 0, n - 1, l, r) - mx.tree_request(1, 0, n - 1, l, r) << "\n";
    }
}