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