Subarray Sum Queries

Problem Statement:

You are given an array of n integers and q queries. Each query consists of two integers l and r (1-indexed) and asks you to calculate the sum of the subarray from index l to r inclusive.

Your task is to efficiently process these queries and output the sum for each query. An optimal way to achieve this is by computing prefix sums first, which allows each query to be answered in constant time.

Note: Use stdin for input and stdout for output.

inputFormat

The input consists of several lines. The first line contains a single integer n — the number of elements in the array. The second line contains n space-separated integers representing the array elements. The third line contains a single integer q — the number of queries. Each of the next q lines contains two space-separated integers l and r representing the 1-indexed start and end positions of a query.

outputFormat

For each query, output the sum of the subarray from index l to r on a separate line.## sample

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

6
14
15