 Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms

• # Faster range queries

Given an array `a` of `n` integers, you are asked to answer `q` queries. All the queries have the form: “What is the sum of elements in the array `a` between indices `[l; r]`?” (both endpoints are inclusive and the indexing starts from 0). This time the number of queries and the size of the array are significantly larger. Can you think of a way to answer those queries faster?

#### Input

The first line of the input contains a single integer `n` - the number of elements in the array (1 ≤ n ≤ ). The next line contains `n` integers separated by a space, that represent the elements of the array .
The following line contains a single integer `q` - the number of queries (1 ≤ q ≤ ). The next `q` lines contain queries of the form .

#### Output

The program should print `q` lines, each of which is the sum of elements in the array `a` between indices (both inclusive).

#### Examples

 Input Output 8 1 2 3 4 5 6 7 8 3 0 4 5 6 5 7 15 13 21