CF1601E.Phys Ed Online

Students of one unknown college don't have PE courses. That's why $q$ of them decided to visit a gym nearby by themselves. The gym is open for $n$ days and has a ticket system. At the $i$-th day, the cost of one ticket is equal to $a_i$. You are free to buy more than one ticket per day.

You can activate a ticket purchased at day $i$ either at day $i$ or any day later. Each activated ticket is valid only for $k$ days. In other words, if you activate ticket at day $t$, it will be valid only at days $t, t + 1, \dots, t + k - 1$.

You know that the $j$-th student wants to visit the gym at each day from $l_j$ to $r_j$ inclusive. Each student will use the following strategy of visiting the gym at any day $i$ ($l_j \le i \le r_j$):

1. person comes to a desk selling tickets placed near the entrance and buy several tickets with cost $a_i$ apiece (possibly, zero tickets);
2. if the person has at least one activated and still valid ticket, they just go in. Otherwise, they activate one of tickets purchased today or earlier and go in.

Note that each student will visit gym only starting $l_j$, so each student has to buy at least one ticket at day $l_j$.

Help students to calculate the minimum amount of money they have to spend in order to go to the gym.

某所不知名大学的学生没有体育课。因此，其中 $q$ 名学生决定自行前往附近的一家健身房。该健身房开放 $n$ 天，并采用门票系统。第 $i$ 天一张门票的价格为 $a_i$。你可以在同一天购买任意数量的门票（包括零张）。

你可以在第 $i$ 天购买的门票于第 $i$ 天或之后任意一天激活。每张已激活的门票仅在激活后连续有效 $k$ 天。换言之，若你在第 $t$ 天激活一张门票，则该门票仅在第 $t, t + 1, \dots, t + k - 1$ 天有效。

已知第 $j$ 名学生希望在第 $l_j$ 天至第 $r_j$ 天（含端点）的每一天都去健身房。每名学生在任意一天 $i$（满足 $l_j \le i \le r_j$）访问健身房时，将采用如下策略：

1. 该人前往入口附近的售票台，以单价 $a_i$ 购买若干张门票（可能为零张）；
2. 若该人手中至少拥有一张已激活且仍在有效期内的门票，则直接入场；否则，从当天或之前购买的门票中激活一张，然后入场。

注意：每名学生仅从第 $l_j$ 天起开始访问健身房，因此每名学生必须在第 $l_j$ 天至少购买一张门票。

请帮助这些学生计算他们为前往健身房所需花费的最少金额。

The first line contains three integers $n$, $q$ and $k$ ($1 \le n, q \le 300\,000$; $1 \le k \le n$) — the number of days, the number of students and the number of days each ticket is still valid.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the cost of one ticket at the corresponding day.

Each of the next $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the segment of days the corresponding student want to visit the gym.

第一行包含三个整数 $n$、$q$ 和 $k$（$1 \le n, q \le 300\,000$；$1 \le k \le n$）——分别表示天数、学生人数以及每张票的有效天数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——表示对应天数一张票的价格。

接下来的 $q$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）——表示对应学生希望去健身房的时间段（天数区间）。

For each student, print the minimum possible amount of money they have to spend in order to go to the gym at desired days.

对于每个学生，输出他们为了在期望的日期去健身房所需花费的最少金额。

Let's see how each student have to spend their money:

• The first student should buy one ticket at day $1$.
• The second student should buy one ticket at day $3$ and two tickets at day $4$. Note that student can keep purchased tickets for the next days.
• The third student should buy one ticket at day $5$.
• The fourth student should buy one ticket at day $7$.
• The fifth student should buy one ticket at day $3$ and one at day $4$.

我们来看看每位学生需要如何花费他们的钱：

• 第一位学生应在第 $1$ 天购买一张票。
• 第二位学生应在第 $3$ 天购买一张票，并在第 $4$ 天购买两张票。注意，学生可以将已购的票保留至后续日期使用。
• 第三位学生应在第 $5$ 天购买一张票。
• 第四位学生应在第 $7$ 天购买一张票。
• 第五位学生应在第 $3$ 天购买一张票，并在第 $4$ 天再购买一张票。