Prefix Sums

Lab C++ Intermediate 20 points

Read n integers and q queries l r (0-based, inclusive). Answer each range sum in O(1) using a prefix-sum vector.

Input

n, the integers, q, then q lines.

Output

q lines.

Example

Input

Output

15
9
3

Sample input available Sample output available

Editor

C++

Hints

prefix[i] = sum of the first i elements; a range sum is a difference of two prefixes.

Solution explanation

One O(n) pass makes every range query O(1).

Show solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n;
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        prefix[i + 1] = prefix[i] + x;
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r + 1] - prefix[l] << "\n";
    }
    return 0;
}

Output

Answer