Problem Description

Define the initial sequence as a sequence in which every number is $0$.

Define one operation as increasing the value of every number in an interval of the sequence by $1$, with the restriction that the length of this interval cannot exceed $m$.

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$, and you need to output the minimum number of operations required to turn an initial sequence of length $r-l+1$ into the subarray $[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 is $a_i$.

The next $q$ lines each contain two integers $l, r$.

Output Format

Output $q$ lines, each containing one integer, indicating 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$.

In the first operation, increase every number in the interval $[1,3]$, that is, the $1$st, $2$nd, and $3$rd numbers, by $1$. After this operation, the sequence becomes $1$ $1$ $1$ $0$ $0$.

In the second operation, increase every number in the interval $[3,5]$, that is, 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\le300$.
• Subtask 4 (10 points): $n,q\le5\times10^3$.
• Subtask 5 (15 points): $m\le5$.
• Subtask 6 (15 points): $m\le100$.
• Subtask 7 (20 points): $n,q\le5\times10^4$.
• Subtask 8 (25 points): no special constraints.

For $100\%$ of the testdata, it is guaranteed that $1\le m\le n\le10^5$, $1\le q\le10^5$, $0\le a_i\le10^9$, and $1\le l\le r\le n$.

Translated by ChatGPT 5