Minimum Operations to Transform Sequence

You are given an initial sequence where every element is 0. In one operation, you can choose a contiguous segment of the sequence whose length does not exceed (m) and add 1 to each element in that segment. Given an array (a) of length (n) (where (a_i) represents the (i)-th element) and (q) queries, each query specifies an interval ([l, r]). For each query, you need to determine the minimum number of operations required to transform an initial sequence of length (r-l+1) (all zeros) into the corresponding subarray (a_l, a_{l+1}, \dots, a_r).

The solution is based on a greedy simulation using a sliding-window technique. For the given subarray, traverse from the left and, at each position, if the current value is less than the target value, perform the required number of operations on an interval of length at most (m) starting at that position. This ensures that the operations are optimally used.

inputFormat

The first line contains three integers (n), (m), and (q) --- the length of the sequence, the maximum allowed segment length for an operation, and the number of queries. The second line contains (n) integers (a_1, a_2, \ldots, a_n), representing the target sequence. Each of the next (q) lines contains two integers (l) and (r) (with (1 \leq l \leq r \leq n)), representing a query.

outputFormat

For each query, output a single integer on a separate line --- the minimum number of operations required.

sample

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

3
5
1