Prefix Sum Queries

Problem Description:

You are given an array of integers. Your task is to answer multiple queries that ask for the sum of the elements in a subarray specified by two indices. To solve this efficiently, you are required to preprocess the array and compute its prefix sum array. The prefix sum array is defined as follows for a 1-indexed array:

Using this prefix sum array, you can answer any query in constant time, where each query consists of two integers, l and r (1-based), and you must output the sum of elements from index l to r (inclusive).

inputFormat

Input Format:

The input is read from standard input (stdin) and has the following format:
1. The first line contains a single integer n, the number of elements in the array.
2. The second line contains n space-separated integers, representing the array elements.
3. The third line contains an integer q, the number of queries.
4. Each of the next q lines contains two space-separated integers, l and r, indicating the query range (1-indexed).

outputFormat

Output Format:

For each query, output on a new line the sum of the elements in the subarray from index l to index r (inclusive).## sample

5
1 2 3 4 5
3
1 3
2 4
1 5

6
9
15