Это экстремальная версия задачи. В этой версии выход для каждого запроса отличается от легкой и сложной версий. Также гарантируется, что \(r \geq l+k-1\) для всех запросов.
Для произвольного массива \(b\) Юнли может выполнять следующую операцию любое количество раз:
- Выбрать индекс \(i\). Установить \(b_i = x\), где \(x\) — любое целое число, которое она желает (\(x\) не ограничено интервалом \([1,n]\)).
Обозначим \(f(b)\) как минимальное количество операций, которые ей нужно выполнить, чтобы в массиве \(b\) существовал последовательный подмассив\(^{\text{∗}}\) длиной не менее \(k\).
Юнли дан массив \(a\) размером \(n\), и она задает вам \(q\) запросов. В каждом запросе вы должны вывести \(\sum_{i=l}^{r-k+1} \sum_{j=i+k-1}^{r} f([a_i, a_{i+1}, \ldots, a_j])\).
Выходные данные
Выведите \(\sum_{i=l}^{r-k+1} \sum_{j=i+k-1}^{r} f([a_i, a_{i+1}, \ldots, a_j])\) для каждого запроса на новой строке.
Примечание
В первом запросе первого набора входных данных мы можем вычислить ответ на запрос следующим образом:
- \(i = 4\) и \(j = 5\): \(f([2, 1])=1\), потому что Юнли может установить \(b_2=3\), что создаст последовательный подмассив размером \(2\) за \(1\) ход.
- \(i = 4\) и \(j = 6\): \(f([2, 1, 2])=0\), потому что уже существует последовательный массив размером \(2\).
- \(i = 5\) и \(j = 6\): \(f([1, 2])=0\), потому что уже существует последовательный массив размером \(2\).
Ответ на этот запрос равен \(1+0+0=1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
7 2 4
1 2 3 2 1 2 3
4 6
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
10 4 8
2 3 6 5 8 9 8 10 10 1
2 7
6 10
1 9
1 6
3 9
4 10
2 10
1 8
10 7 4
3 4 5 3 4 5 9 10 8 9
1 9
2 10
1 10
2 9
|
1
3
3
3
2
7
2
4
8
6
28
7
16
20
32
19
18
15
26
9
|