Дана перестановка\(^{\dagger}\) \(p_1, p_2, \ldots, p_n\) целых чисел от \(1\) до \(n\).
Вы можете изменять текущую перестановку, применяя к ней следующую операцию несколько (возможно, ноль) раз:
- выбрать произвольное \(x\) (\(2 \le x \le n\));
- создать новую перестановку так:
- сначала выписать все элементы \(p\), значения которых меньше \(x\), без изменения их порядка;
- затем выписать все элементы \(p\), значения которых больше или равны \(x\), без изменения их порядка;
- заменить \(p\) этой полученной перестановкой.
Например, если изначально перестановка была \([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\)).
Примечание
В первом наборе входных данных \(n = 1\) и \(p_1 = 1\), так что делать нечего.
Во втором наборе входных данных можно выбрать \(x = 2\), и мы сразу получим \(p_1 = 1\), \(p_2 = 2\).
В третьем наборе входных данных кратчайшей последовательностью операций является, например, следующая:
- \(x = 4\): \([6, 4, 3, 5, 2, 1] \rightarrow [3, 2, 1, 6, 4, 5]\);
- \(x = 6\): \([3, 2, 1, 6, 4, 5] \rightarrow [3, 2, 1, 4, 5, 6]\);
- \(x = 3\): \([3, 2, 1, 4, 5, 6] \rightarrow [2, 1, 3, 4, 5, 6]\);
- \(x = 2\): \([2, 1, 3, 4, 5, 6] \rightarrow [1, 2, 3, 4, 5, 6]\).