Fibonacci Sum Queries

You are given an integer array and several queries. For each query you need to calculate the sum of Fibonacci numbers corresponding to the array elements in the given range.

The Fibonacci sequence is defined as follows:

(F(0)=0,\ F(1)=1) and for (n \ge 2), (F(n)=F(n-1)+F(n-2)).

</p>

You first precompute the Fibonacci number for each distinct element in the array so that queries can be answered quickly. Then, by using prefix sums, answer each query that asks for the sum of Fibonacci numbers in a subarray.

Example 1:
Input: n = 5, elements = [3, 1, 4, 1, 5], queries = [(1, 3), (2, 5), (1, 5)]
Output: 6, 10, 12

Example 2:
Input: n = 4, elements = [0, 1, 2, 3], queries = [(1, 2), (2, 4)]
Output: 1, 4

Example 3:
Input: n = 3, elements = [10, 10, 10], queries = [(1, 3)]
Output: 165

inputFormat

The input is given in the following format:

1. The first line contains an integer \(n\) representing the number of elements in the array.
2. The second line contains \(n\) space-separated integers.
3. The third line contains an integer \(m\) representing the number of queries.
4. The next \(m\) lines each contain two space-separated integers \(l\) and \(r\) (1-indexed) denoting a query for the sum of Fibonacci numbers from index \(l\) to \(r\) in the array.

outputFormat

For each query, print the sum of Fibonacci numbers corresponding to the elements in the specified subarray. Each answer should be on a new line.

## sample

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

6
10
12

</p>