Range sums with prefix sums

You are given an array of n integers and q queries. Each query l r (0-based, 0 ≤ l ≤ r < n) asks for a[l] + a[l+1] + … + a[r].

Answer every query, and compare two strategies by counting operations (never measure time):

• Naive: add up the elements of each range directly. Count one addition per element added, i.e. r - l + 1 per query.
• Prefix sums: first build prefix[0..n] with prefix[0] = 0 and prefix[i+1] = prefix[i] + a[i] (count n operations), then answer each query as prefix[r+1] - prefix[l] (count 1 operation per query).

Input: n, then n integers, then q, then q lines l r. Print one line per query, then the two counts, exactly as below. Sums can exceed the int range — use long.

For the input

5
3 -1 4 1 5
3
0 4
1 3
2 2

the output is

sum(0..4) = 12
sum(1..3) = 4
sum(2..2) = 4
Naive additions: 9
Prefix-sum operations: 8

Both strategies must give the same sums; print the prefix-sum answer.