sqrtTREE

#include <bits/stdc++.h>
//#pragma GCC optimize ("-O3,unroll-loops")
#define FORN(n) for(int i = 0; i < n; i++)
#define nl '\n'
#define INF 1e9
#define F first
#define S second
#define PB push_back
#define INS insert
#define ER erase
using namespace std;

template<typename T> inline ostream & operator<< (ostream &_out, vector<T> &_v) { for (auto &_i : _v) { _out << _i << " "; } return _out; }
template<typename T> inline istream & operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }

mt19937 rnd(42);

typedef long long ll;
typedef vector<long long> vl;
typedef vector<vector<long long> > vvl;
typedef pair<long long, long long> pl;

int mlog(int n) {
    int k = 0;
    while ((1 << k) < n)
        k++;
    return k;
}

class sqrtTree {
    int n, h;
    vector<vvl> pref;
    vector<vvl> suff;
    vector<vvl> between;
    vl squares;
    public:
        sqrtTree(vector<ll>& a);
        bool valid(int l, int r, int blcksz);
        pl findvalid(int l, int r);
        ll request(int l, int r);
};

sqrtTree::sqrtTree(vector<ll>& a) {
    int csz, ccnt, csplit;
    n = 1 << mlog(a.size());
    h = (int)ceil(log2(log2((float)n)))+1;
    a.resize(n, 0);
    pref.resize(h), suff.resize(h), between.resize(h), squares.resize(h);
    csz = n, csplit = n;
    for (int i = 0; i < h; i++) {
        squares[h-i-1] = csz;
        ccnt = n / csz;
        csplit /= csz;
        pref[i].resize(ccnt, vector<ll>(csz)), suff[i].resize(ccnt, vector<ll>(csz)), between[i].resize(ccnt, vector<ll>(csplit));
        for (int cblck = 0; cblck < ccnt; cblck++) {
            pref[i][cblck][0] = a[cblck*csz], suff[i][cblck][csz-1] = a[cblck*csz+csz-1];
            for (int j = 1; j < csz; j++)
                pref[i][cblck][j] = pref[i][cblck][j-1]+a[cblck*csz+j], suff[i][cblck][csz-1-j] = suff[i][cblck][csz-j] + a[cblck*csz+csz-1-j];
        }
        for (int cblck = 0; cblck < ccnt; cblck++) {
            between[i][cblck][cblck%csplit] = pref[i][cblck][csz-1];
            for (int j = cblck+1; j < ccnt && j%csplit < csplit && j%csplit != 0; j++)
                between[i][cblck][j%csplit] = between[i][cblck][j%csplit-1] + pref[i][j][csz-1];
        }
        csplit = csz;
        csz = 1 << mlog(sqrt(csz));
    }
    return;
}

bool sqrtTree::valid(int l, int r, int blcksz) {
    if (blcksz > 2 && l/blcksz == r/blcksz && l%blcksz != 0 && r%blcksz != blcksz - 1) return false;
    return true;
}

pl sqrtTree::findvalid(int l, int r) {
    int lh = 0, rh = h, mh;
    while (rh - lh > 1) {
        mh = (rh+lh)/2;
        if (valid(l, r, squares[mh]))
            lh = mh;
        else
            rh = mh;
    }
    if (l % squares[lh] == 0) return {l/squares[lh], lh};
    else return {l/squares[lh]+1, lh};
}

ll sqrtTree::request(int l, int r) {
    if (l > r) swap(l, r);
    pl val = findvalid(l, r);
    ll ans = 0;
    int lsqind = val.F*squares[val.S];
    if (l < lsqind) ans += suff[h-val.S-1][val.F-1][squares[val.S]-lsqind+l];
    int rsqind = lsqind + ((r-lsqind)/squares[val.S])*squares[val.S];
    if (rsqind != lsqind) ans += between[h-val.S-1][val.F][rsqind/squares[val.S]-1];
    if (r >= rsqind) ans += pref[h-val.S-1][rsqind/squares[val.S]][r-rsqind];
    return ans;
}

void read(vector<ll> &a) {
    int n; cin >> n;
    a.resize(n);
    cin >> a;
    return;
}

void requests(sqrtTree& s) {
    int m; cin >> m;
    int u, v;
    FORN(m) {
        cin >> u >> v;
        cout << s.request(u, v) << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    vector<ll> a;
    read(a);
    sqrtTree st(a);
    requests(st);
    return 0;
}