308464: CF1525B. Permutation Sort
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Permutation Sort
题意翻译
你需要对一个长度为 $n$ 的全排列进行一些操作,每次你都可以选择一个区间(当然是连续的)进行任意的交换(你想把这个区间排成什么样都行),请问最少需要多少次操作才能使得这个排列是升序的?题目描述
You are given a permutation $ a $ consisting of $ n $ numbers $ 1 $ , $ 2 $ , ..., $ n $ (a permutation is an array in which each element from $ 1 $ to $ n $ occurs exactly once). You can perform the following operation: choose some subarray (contiguous subsegment) of $ a $ and rearrange the elements in it in any way you want. But this operation cannot be applied to the whole array. For example, if $ a = [2, 1, 4, 5, 3] $ and we want to apply the operation to the subarray $ a[2, 4] $ (the subarray containing all elements from the $ 2 $ -nd to the $ 4 $ -th), then after the operation, the array can become $ a = [2, 5, 1, 4, 3] $ or, for example, $ a = [2, 1, 5, 4, 3] $ . Your task is to calculate the minimum number of operations described above to sort the permutation $ a $ in ascending order.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 2000 $ ) — the number of test cases. The first line of the test case contains a single integer $ n $ ( $ 3 \le n \le 50 $ ) — the number of elements in the permutation. The second line of the test case contains $ n $ distinct integers from $ 1 $ to $ n $ — the given permutation $ a $ .
输出格式
For each test case, output a single integer — the minimum number of operations described above to sort the array $ a $ in ascending order.
输入输出样例
输入样例 #1
3
4
1 3 2 4
3
1 2 3
5
2 1 4 5 3
输出样例 #1
1
0
2