Дана перестановка \(p\) длины \(n\) и целое число \(k\). Рассмотрим перестановку \(q\) длины \(n\) такую, что для любых целых чисел \(i\) и \(j\), где \(1 \le i < j \le n\), выполняется \(\)p_{q_i} \le p_{q_j} + k.\(\)
Найдите минимально возможное количество инверсий, которое может быть в перестановке \(q\).
Перестановкой является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Инверсия в перестановке \(a\) — это пара индексов \(i\) и \(j\) (\(1 \le i, j \le n\)), такая, что \(i < j\), но \(a_i > a_j\).
Выходные данные
Выведите минимально возможное количество инверсий, которое может быть в перестановке \(q\).
Примечание
В первом примере единственный вариант перестановки \(q = [1]\) (\(0\) инверсий). Тогда \(p_{q_1} = 1\).
Во втором примере единственный вариант с \(1\) инверсией — \(q = [1, 3, 2]\). Тогда \(p_{q_1} = 2\), \(p_{q_2} = 1\), \(p_{q_3} = 3\).
В третьем примере один из возможных вариантов с \(6\) инверсиями — \(q = [3, 4, 5, 1, 2]\). Тогда \(p_{q_1} = 3\), \(p_{q_2} = 2\), \(p_{q_3} = 1\), \(p_{q_4} = 5\), \(p_{q_5} = 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
1
|
0
|
|
2
|
3 1
2 3 1
|
1
|
|
3
|
5 2
5 4 3 2 1
|
6
|
|
4
|
10 3
5 8 6 10 2 7 4 1 9 3
|
18
|