Pinely Round 2 (Div. 1 + Div. 2) |
---|
Закончено |
Дана перестановка$$$^{\dagger}$$$ $$$p_1, p_2, \ldots, p_n$$$ целых чисел от $$$1$$$ до $$$n$$$.
Вы можете изменять текущую перестановку, применяя к ней следующую операцию несколько (возможно, ноль) раз:
Например, если изначально перестановка была $$$[6, 4, 3, 5, 2, 1]$$$ и выбрано $$$x = 4$$$, то сначала нужно выписать $$$[3, 2, 1]$$$, затем справа дописать $$$[6, 4, 5]$$$. Так, изначальная перестановка будет заменена на $$$[3, 2, 1, 6, 4, 5]$$$.
Найдите наименьшее число операций, необходимое для того, чтобы достичь равенства $$$p_i = i$$$ для всех $$$i = 1, 2, \ldots, n$$$. Можно показать, что ответ всегда существует.
$$$^{\dagger}$$$ Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100\,000$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$). Гарантируется, что $$$p_1, p_2, \ldots, p_n$$$ является перестановкой.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$100\,000$$$.
Для каждого набора входных данных выведите ответ на отдельной строке.
51122 166 4 3 5 2 133 1 21910 19 7 1 17 11 8 5 12 9 4 18 14 2 6 15 3 16 13
0 1 4 1 7
В первом наборе входных данных $$$n = 1$$$ и $$$p_1 = 1$$$, так что делать нечего.
Во втором наборе входных данных можно выбрать $$$x = 2$$$, и мы сразу получим $$$p_1 = 1$$$, $$$p_2 = 2$$$.
В третьем наборе входных данных кратчайшей последовательностью операций является, например, следующая:
Название |
---|