Вам дана перестановка \(a\) состоящая из \(n\) чисел \(1\), \(2\), ..., \(n\) (перестановка — это массив, в котором каждый элемент от \(1\) до \(n\) встречается ровно один раз).
Вы можете выполнять операцию следующего вида — выбрать подмассив (непрерывный подотрезок) \(a\) и переставить в нем элементы произвольным образом. Но такую операцию нельзя применить ко всему массиву целиком.
Например, \(a = [2, 1, 4, 5, 3]\) и мы хотим применить операцию к подмассиву \(a[2, 4]\) (подмассиву, содержащему все элементы от \(2\)-го до \(4\)-го), тогда после операции массив может иметь вид \(a = [2, 5, 1, 4, 3]\), или, например, \(a = [2, 1, 5, 4, 3]\).
Ваша задача — определить минимальное количество вышеописанных операций, позволяющих отсортировать перестановку \(a\) в возрастающем порядке.
Выходные данные
Для каждого набора выходных данных выведите одно целое число — минимальное количество вышеописанных операций, позволяющих отсортировать перестановку \(a\) по возрастанию.
Примечание
В объяснениях \(a[i, j]\) означает подмассив \(a\), который начинается с \(i\)-го элемента и заканчивается \(j\)-м элементом.
В первом наборе входных данных из условия можно выбрать подмассив \(a[2, 3]\) и поменять в нем элементы местами.
Во втором наборе входных данных перестановка уже отсортирована, поэтому операции применять не нужно.
В третьем наборе входных данных можно выбрать подмассив \(a[3, 5]\) и превратить \(a\) в \([2, 1, 3, 4, 5]\), а затем выбрать подмассив \(a[1, 2]\) и превратить \(a\) в \([1, 2, 3, 4, 5]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
1 3 2 4
3
1 2 3
5
2 1 4 5 3
|
1
0
2
|