Challenge: Range Sum Questions

Lab C++ Beginner 10 points

Read n numbers, then q questions i j. For each, print the sum of items from index i to j (both included, from 0). Use prefix sums.

Input

Line 1: n. Line 2: n whole numbers. Line 3: q. Then q lines i j.

Output

One total per question.

Example

Input

Output

10
19
7

Sample input available Sample output available

Editor

C++

Hints

prefix[0] = 0 and prefix[i + 1] = prefix[i] + v[i].

sum(i..j) = prefix[j + 1] - prefix[i].

Solution explanation

O(n) to prepare, then O(1) per question.

Show solution

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

int main() {
    int n;
    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;
    }
    int q;
    cin >> q;
    while (q--) {
        int i, j;
        cin >> i >> j;
        cout << prefix[j + 1] - prefix[i] << endl;
    }
    return 0;
}

Output

Answer