Задача №114751. Онлайн-курс по физкультуре
Девочка Лола учится в ПТУ, поэтому у нее нет обязательных занятий по физкультуре. Чтобы исправить это недоразумение, Лола решила записаться в спортзал. В спортзале действует система абонементов, в \(i\)-й из \(n\) дней известна цена покупки абонемента \(a_i\). Разрешается покупать более одного абонемента за день.
Купленный в день \(i\) абонемент можно активировать в день \(i\) или позднее. Каждый из абонементов после активации будет дейстовать \(k\) дней, то есть активированный в день \(t\) абонемент будет действовать в дни с номерами \(t, t + 1, ... , t + k - 1\).
Лола — очень экономная девочка, поэтому она заранее планирует \(q\) независимых сценариев похода в спортзал, в \(i\)-м сценарии она будет ходить в зал в дни с номерами от \(l_i\) до \(r_i\) включительно. Лола не станет покупать абонементы до дня \(l_i\). Помогите ей посчитать, какую минимальную сумму придется потратить, чтобы посещать зал в эти дни.
В первой строке даны 3 целых числа \(n, q, k\) (\(1 \le n, q \le 300\,000, 1 \le k \le n\)) — число дней, число сценариев и длительность абонемента.
Во второй строке даны \(n\) целых чисел \(a_1, a_2, ..., a_n\) (\(1 \le a_i \le 10^9\)).
В следующих \(q\) строках даны два целых числа \(l_i, r_i\) (\(1 \le l_i \le r_i \le n\)) — описания сценариев.
Для каждого сценария выведите минимальную сумму, необходимую для посещения спортзала.
- В первом сценарии Лола купит сертификат в день \(1\).
- Во втором сценарии она купит один сертификат в день \(3\) и два сертификата в день \(4\). Обратите внимание, что она не обязана использовать их в тот же день.
- В третьем сценарии Лола купит сертификат в день \(5\).
- В четвертом сценарии Лола купит сертификат в день \(7\).
- В пятом сценарии Лола купит по одному сертификату в дни \(3\) и \(4\).
7 5 2 2 15 6 3 7 5 6 1 2 3 7 5 5 7 7 3 5
2 12 7 6 9