定义初始数列为每个数字都为 $0$ 的数列。
定义一次操作为将数列的一个区间中每一个数的值增加 $1$，规定该区间的长度不能超过 $m$。
给定一个长度为 $n$ 的数列 $a$，第 $i$ 个数为 $a_i$。
你需要回答 $q$ 次询问。每次询问给定 $l,r$，你需要回答将一个长度为 $r-l+1$ 的初始数列变为 $a$ 中的 $[l,r]$（即数列 $a_l$, $a_{l+1}$, $\cdots$, $a_r$）至少需要多少次操作。
输入格式
第一行三个整数 $n,m,q$。
第二行 $n$ 个整数，第 $i$ 个为 $a_i$。
接下来 $q$ 行，每行两个整数，表示 $l,r$。
输出格式
$q$ 行，每行一个整数，表示至少需要的操作次数。
样例数据
样例 1 输入
5 4 1
1 1 2 1 1
1 5样例 1 输出
2样例 1 解释
一个长度为 $5$ 的初始数列为 $0$ $0$ $0$ $0$ $0$。
第一次操作为，将区间 $[1,3]$ 中每一个数，即第 $1$、$2$、$3$ 个数的值分别增加 $1$。经过该操作后，数列变为 $1$ $1$ $1$ $0$ $0$。
第二次操作为，将区间 $[3,5]$ 中每一个数，即第 $3$、$4$、$5$ 个数的值分别增加 $1$。经过该操作后，数列变为 $1$ $1$ $2$ $1$ $1$。
样例 2 输入
10 3 3
4 8 1 2 9 7 4 1 3 5
1 10
3 8
5 5样例 2 输出
22
10
9子任务
- 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）：无特殊限制。
对于 $100\%$ 的数据，保证 $1\le m\le n\le10^5$，$1\le q\le10^5$，$0\le a_i\le10^9$，$1\le l\le r\le n$。