Minimum Operations to Transform Sequence

We are given a sequence (a) of length (n) that is obtained starting from an initial sequence of zeros by a series of operations. In each operation, you choose a contiguous subarray (interval) with length at most (m) and add (1) to every number in that interval.

For example, one allowed operation is to pick an interval ([l, r]) with (r - l + 1 \le m) and then update (a_l, a_{l+1}, \dots, a_r) by adding 1 to each.

You are given (q) queries. In each query you are given two integers (l) and (r). Consider the target sequence (b = [a_l, a_{l+1}, \dots, a_r]) (with length (L=r-l+1)). Starting from an initial sequence of zeros of length (L), compute the minimum number of operations required to transform it into (b) using the allowed operations.

It can be shown that for any target sequence (b) that comes from valid operations the following greedy strategy is optimal:

We simulate from left to right maintaining the extra increments already applied to the current position (using a difference array for the operations’ effect). For each position (i) (0-indexed) in (b), let (current) be the cumulative increments applied so far. If (b[i] > current), we need (\Delta = b[i] - current) additional operations starting at index (i). Each such operation adds (1) to all positions in the interval from (i) to (\min(i+m-1, L-1)) and is simulated by adding (\Delta) to (current) and subtracting (\Delta) from the effect beyond index (i+m-1).

Your task is to answer all queries correctly.

Note: All formulas are written in (\LaTeX) format.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) (the length of the sequence, the maximum allowed length of an operation's interval, and the number of queries).

The second line contains \(n\) non-negative integers \(a_1, a_2, \dots, a_n\) separated by spaces. It is guaranteed that \(a\) can be obtained from an initial zero sequence using the allowed operations.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) (1-indexed), representing a query to determine the minimum number of operations needed to obtain the subarray \([a_l, a_{l+1}, \dots, a_r]\) from an initial zero sequence of the same length.

outputFormat

For each query, output a single integer representing the minimum number of operations required to transform the initial zero sequence to the target subarray.

sample

5 3 3
0 1 1 2 1
1 3
2 5
1 5

1
2
2