Background

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?

Problem Description

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$).

Input Format

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 Format

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

5 4 1
1 1 2 1 1
1 5

2

10 3 3
4 8 1 2 9 7 4 1 3 5
1 10
3 8
5 5

22
10
9

Hint

"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