Вам дана перестановка \(p\) длины \(n\), массив из \(m\) различных целых чисел \(a_1, a_2, \ldots, a_m\) (\(1 \le a_i \le n\)) и целое число \(d\).
Пусть \(\mathrm{pos}(x)\) — индекс элемента \(x\) в перестановке \(p\). Массив \(a\) не является хорошим, если
- \(\mathrm{pos}(a_{i}) < \mathrm{pos}(a_{i + 1}) \le \mathrm{pos}(a_{i}) + d\) для всех \(1 \le i < m\).
Например, при перестановке \(p = [4, 2, 1, 3, 6, 5]\) и \(d = 2\):
- \(a = [2, 3, 6]\) — это не хороший массив.
- \(a = [2, 6, 5]\) является хорошим, потому что \(\mathrm{pos}(a_1) = 2\), \(\mathrm{pos}(a_2) = 5\), поэтому условие \(\mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d\) не выполняется.
- \(a = [1, 6, 3]\) является хорошим, потому что \(\mathrm{pos}(a_2) = 5\), \(\mathrm{pos}(a_3) = 4\), поэтому условие \(\mathrm{pos}(a_2) < \mathrm{pos}(a_3)\) не выполняется.
За один ход можно поменять местами два соседних элемента перестановки \(p\). Какое минимальное количество ходов нужно сделать, чтобы массив \(a\) стал хорошим? Можно показать, что всегда существует последовательность ходов, при которой массив \(a\) становится хорошим.
Перестановка — это массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) дважды встречается в массиве) и \([1,3,4]\) также не является перестановкой (\(n=3\), но в массиве есть \(4\)).
Выходные данные
Для каждого набора входных данных выведите минимальное количество ходов, необходимое для того, чтобы массив \(a\) стал хорошим.
Примечание
В первом наборе, \(pos(a_1)=1\), \(pos(a_2)=3\). Входных данных можно поступить следующим образом: поменять местами \(p_3\) и \(p_4\). После этого массив \(a\) будет хорошим, так как условие \(\mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d\) не будет выполнено.
Во втором наборе, \(pos(a_1)=1\), \(pos(a_2)=4\). Можно выполнить \(3\) таких хода:
- Поменять местами \(p_3\) и \(p_4\).
- Поменять местами \(p_2\) и \(p_3\).
- Поменять местами \(p_1\) и \(p_2\).
После этих перемещений перестановка
\(p\) будет иметь вид
\([2,5,4,3,1]\). Массив
\(a\) будет
хорошим, потому что условие
\(\mathrm{pos}(a_1) < \mathrm{pos}(a_2)\) не будет выполнено. Можно показать, что массив
\(a\) нельзя сделать
хорошим за меньшее число ходов.
В третьем наборе, \(pos(a_1)=1\), \(pos(a_2)=3\), \(pos(a_3)=5\). Ходов может быть \(2\):
- Поменять местами \(p_4\) и \(p_5\).
- Поменять местами \(p_3\) и \(p_4\).
После этих перемещений перестановка
\(p\) будет иметь вид
\([3,4,2,1,5]\). Массив
\(a\) будет
хорошим, потому что условие
\(\mathrm{pos}(a_2) < \mathrm{pos}(a_3)\) не будет выполнено. Можно показать, что массив
\(a\) нельзя сделать
хорошим за меньшее количество ходов.
В четвертом наборе, \(pos(a_1)=2\), \(pos(a_2)=1\). Массив \(a\) уже хороший.
В пятом наборе, \(pos(a_1)=2\), \(pos(a_2)=5\). Ходов может быть \(2\):
- Поменять местами \(p_1\) и \(p_2\).
- Поменять местами \(p_5\) и \(p_6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 2 2
1 2 3 4
1 3
5 2 4
5 4 3 2 1
5 2
5 3 3
3 4 1 5 2
3 1 2
2 2 1
1 2
2 1
6 2 4
1 2 3 4 5 6
2 5
|
1
3
2
0
2
|