P8182 "EZEC-11" Snow Magic

Muxii is a snow mage. As long as he waves his wand and chants a mysterious spell, snowflakes will fall from the sky and slowly build up a thick layer of snow on the ground. Because Muxii's magic is so powerful, God appointed Muxii to control all the snow in the world. One day, God gave Muxii a task: he needs to make it snow on a piece of ground of length $n$. The snow depth at position $i$ must reach $a_i$ ($a_i \ge 0$; “reach $a_i$” means it can be neither less than nor greater than $a_i$). However, what God does not know is that Muxii's ability is limited: each time he casts a spell, he can only make it snow for 1 second on an interval of length $\le m$, increasing the snow depth in that interval by $1$. Since the task is urgent, Muxii wants to know: to complete the task for some interval, how many spells does he need to cast at minimum?

Define the initial sequence as a sequence where every number is $0$. Define one operation as increasing every number in an interval of the sequence by $1$, with the restriction that the length of the interval cannot exceed $m$. You are given a sequence $a$ of length $n$, where the $i$-th number is $a_i$. You need to answer $q$ queries. In each query, you are given $l, r$. You need to output the minimum number of operations required to transform an initial sequence of length $r - l + 1$ into $[l, r]$ of $a$ (that is, the sequence $a_l, a_{l+1}, \cdots, a_r$).

The first line contains three integers $n, m, q$. The second line contains $n$ integers, where the $i$-th one is $a_i$. The next $q$ lines each contain two integers $l, r$.

Output $q$ lines, each containing one integer, the minimum number of operations.

**"Sample 1 Explanation"** An initial sequence of length $5$ is $0$ $0$ $0$ $0$ $0$. The first operation increases every number in interval $[1, 3]$, i.e. the $1$st, $2$nd, and $3$rd numbers, by $1$. After this operation, the sequence becomes $1$ $1$ $1$ $0$ $0$. The second operation increases every number in interval $[3, 5]$, i.e. the $3$rd, $4$th, and $5$th numbers, by $1$. After this operation, the sequence becomes $1$ $1$ $2$ $1$ $1$. **"Constraints and Notes"** - Subtask 1 (1 point): $m = 1$. - Subtask 2 (4 points): $m = n$. - Subtask 3 (10 points): $n, q \le 300$. - Subtask 4 (10 points): $n, q \le 5 \times 10^3$. - Subtask 5 (15 points): $m \le 5$. - Subtask 6 (15 points): $m \le 100$. - Subtask 7 (20 points): $n, q \le 5 \times 10^4$. - Subtask 8 (25 points): No special constraints. For $100\%$ of the testdata, it is guaranteed that $1 \le m \le n \le 10^5$, $1 \le q \le 10^5$, $0 \le a_i \le 10^9$, $1 \le l \le r \le n$. Translated by ChatGPT 5