Вам дан массив \(a\) из \(n\) целых чисел и целое число \(k\) (\(2 \le k \le n\)), где элементы массива обозначаются как \(a_i\) (\(0 \le i < n\)). Выполните операцию \(z\) определённую ниже над \(a\) и выведите значение \(z(a,k)\) по модулю \(10^{9}+7\).
function z(array a, integer k): if length(a) < k: return 0 else: b = empty array ans = 0 for i = 0 .. (length(a) - k): temp = a[i] for j = i .. (i + k - 1): temp = max(temp, a[j]) append temp to the end of b ans = ans + temp return ans + z(b, k)
Первая строка входных данных содержит два целых числа \(n\) и \(k\) (\(2 \le k \le n \le 10^6\)) — длина исходного массива \(a\) и параметр \(k\).
Вторая строка содержит \(n\) целых чисел \(a_0, a_1, \ldots, a_{n - 1}\) (\(1 \le a_{i} \le 10^9\)) — элементы массива \(a\).
Выведите одно целое число — значение \(z(a,k)\) взятое по модулю \(10^9+7\).
В первом примере:
Значит, ответ равен \(19+10+0=29\).
Во втором примере:
Значит, ответ равен \(25+9+0=34\).
3 2 9 1 10
29
5 3 5 8 7 1 9
34
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач