Range Sum of Differences
You are given an array of N integers A. You will also be given Q queries. Each query consists of a range [L, R] (1-indexed). For each query, calculate the sum of the absolute differences between adjacent elements in the array, from index L to R-1. That is, compute the sum of |A[i+1] - A[i]| for i from L to R-1.
For example, if the array is [3, 1, 4, 1, 5, 9] and a query is for the range [2, 5], you need to calculate |A[2]-A[1]| + |A[3]-A[2]| + |A[4]-A[3]|. Note that indices are 0-based in the array, so this would be |A[1]-A[0]| + |A[2]-A[1]| + |A[3]-A[2]| if we use 0-based indexing for the calculation, corresponding to the range [1, 3] of original array indices if query was [2, 5]. If the range [L, R] means that R is the last index of the pair, then indices i go from L up to R-1.
Let's clarify the indexing: for a query [L, R], calculate the sum of |A[i] - A[i-1]| for i from L to R. The array A has indices from 0 to N-1. The query range [L, R] uses 1-based indexing, meaning it refers to array elements A[L-1] through A[R-1]. The differences are between adjacent elements, so we consider pairs (A[i-1], A[i]) where both i-1 and i are within the 0-indexed range [L-1, R-1]. This means we sum |A[i] - A[i-1]| for i from L to R-1.
Example: A = [3, 1, 4, 1, 5, 9], N=6. Query [L=2, R=5]. This refers to elements A[1], A[2], A[3], A[4] (which are 1, 4, 1, 5). We want sum of differences between adjacent elements UP TO index R-1=4. So we consider indices i from L=2 to R-1=4. These are i=2, i=3, i=4. We calculate |A[2]-A[1]| + |A[3]-A[2]| + |A[4]-A[3]| = |4-1| + |1-4| + |5-1| = 3 + 3 + 4 = 10.
Input
The first line contains an integer N (1 <= N <= 1000), the size of the array. The second line contains N space-separated integers A_0, A_1, ..., A_{N-1} (-1000 <= A_i <= 1000). The third line contains an integer Q (1 <= Q <= 1000), the number of queries. Each of the next Q lines contains two space-separated integers L and R (1 <= L < R <= N).
Output
For each query [L, R], print the calculated sum on a new line.
Constraints
1 <= N <= 1000 -1000 <= A_i <= 1000 1 <= Q <= 1000 1 <= L < R <= N
Example 1
6 3 1 4 1 5 9 3 2 5 1 6 4 5
10 16 4
Query 1: range [2, 5] -> elements A[1]..A[4] are [1, 4, 1, 5]. Differences are |4-1|, |1-4|, |5-1|. Sum = 3 + 3 + 4 = 10. Query 2: range [1, 6] -> elements A[0]..A[5] are [3, 1, 4, 1, 5, 9]. Differences are |1-3|, |4-1|, |1-4|, |5-1|, |9-5|. Sum = 2 + 3 + 3 + 4 + 4 = 16. Query 3: range [4, 5] -> ele
Example 2
4 10 20 15 25 2 1 3 2 4
15 15
Query 1: range [1, 3] -> elements A[0]..A[2] are [10, 20, 15]. Differences are |20-10|, |15-20|. Sum = 10 + 5 = 15. Query 2: range [2, 4] -> elements A[1]..A[3] are [20, 15, 25]. Differences are |15-20|, |25-15|. Sum = 5 + 10 = 15.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
6 3 1 4 1 5 9 3 2 5 1 6 4 5
4 10 20 15 25 2 1 3 2 4