Это сложная версия задачи. В этой версии гарантируется, что \(r \geq l+k-1\) для всех запросов.
Для произвольного массива \(b\) Юнли может выполнять следующую операцию любое количество раз:
- Выбрать индекс \(i\). Присвоить \(b_i = x\), где \(x\) — любое целое число, которое она хочет (\(x\) не ограничено интервалом \([1,n]\)).
Обозначим \(f(b)\) как минимальное количество операций, которые ей нужно выполнить, чтобы в массиве \(b\) существовал последовательный подмассив\(^{\text{∗}}\) длиной не менее \(k\).
Юнли дан массив \(a\) размером \(n\), и она задает вам \(q\) запросов. В каждом запросе вы должны вывести \(\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])\).
Выходные данные
Выведите \(\sum_{j=l+k-1}^{r} f([a_l, a_{l+1}, \ldots, a_j])\) для каждого запроса на новой строке.
Примечание
Во втором запросе первого набора входных данных мы вычисляем следующие значения функции:
- \(f([2,3,2,1,2])=3\), потому что Юнли может присвоить \(b_3=4\), \(b_4=5\) и \(b_5=6\), сделав последовательный подмассив размером \(5\) за \(3\) хода.
- \(f([2,3,2,1,2,3])=2\), потому что мы можем присвоить \(b_3=0\) и \(b_2=-1\), сделав последовательный подмассив размером \(5\) за \(2\) хода (начиная с позиции \(2\)).
Ответ на этот запрос равен \(3+2=5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
7 5 3
1 2 3 2 1 2 3
1 7
2 7
3 7
8 4 2
4 3 1 1 2 4 3 2
3 6
1 5
5 4 2
4 5 1 2 3
1 4
1 5
|
6
5
2
2
5
2
3
|