Simply Strange Sort

题意翻译

### 题目描述 给定一个长度为 $n$ 的数组 $a$。 我们用以下方法排序： 我们定义一个函数 $f(i)(1\le i\le n-1)$，如果 $a_i>a_{i+1}$，则交换 $a_i$ 和 $a_{i+1}$。 从 $1$ 开始操作。对于第 $i(1\le i\le n)$ 操作，如果 $i$ 是奇数，则执行 $f(1),f(3),\ldots,f(n-1)$。否则执行 $f(2),f(4),\ldots,f(n-2)$。 请求出：多少次操作后，这个数列是递增的的？ ### 输入格式 包含 $T$ 组样例。 第一行包含 $1$ 个整数 $n$，表示数列长度。 第二行包含 $n$ 个整数，第 $i(1\le i \le n)$ 表示 $a_i$。 ### 输出格式 仅一行，包含一个数 $ans$。表示第 $ans$ 次操作后排序完成。（如果已经排序完成，则输出 $0$）。 ### 说明/提示 第一组样例排列变化如下： - 第 $1$ 次操作结束后：$[2, 3, 1]$。 - 第 $2$ 次操作结束后：$[2, 1, 3]$。 - 第 $3$ 次操作结束后：$[1, 2, 3]$。 第二组样例排列变化如下： - 第 $1$ 次操作结束后：$[4,5,1,7,2,3,6]$。 - 第 $2$ 次操作结束后：$[4, 1, 5, 2, 7, 3, 6]$。 - 第 $3$ 次操作结束后：$[1, 4, 2, 5, 3, 7, 6]$。 - 第 $4$ 次操作结束后：$[1, 2, 4, 3, 5, 6, 7]$。 - 第 $5$ 次操作结束后：$[1, 2, 3, 4, 5, 6, 7]$。 第三组样例无需排序，答案为 $0$。 【数据规模】 $1\le T\le 100,1\le \sum n \le999,1\le a_i \le n$。 保证 $n$ 为奇数。

题目描述

You have a permutation: an array $ a = [a_1, a_2, \ldots, a_n] $ of distinct integers from $ 1 $ to $ n $ . The length of the permutation $ n $ is odd. Consider the following algorithm of sorting the permutation in increasing order. A helper procedure of the algorithm, $ f(i) $ , takes a single argument $ i $ ( $ 1 \le i \le n-1 $ ) and does the following. If $ a_i > a_{i+1} $ , the values of $ a_i $ and $ a_{i+1} $ are exchanged. Otherwise, the permutation doesn't change. The algorithm consists of iterations, numbered with consecutive integers starting with $ 1 $ . On the $ i $ -th iteration, the algorithm does the following: - if $ i $ is odd, call $ f(1), f(3), \ldots, f(n - 2) $ ; - if $ i $ is even, call $ f(2), f(4), \ldots, f(n - 1) $ . It can be proven that after a finite number of iterations the permutation will be sorted in increasing order. After how many iterations will this happen for the first time?

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 3 \le n \le 999 $ ; $ n $ is odd) — the length of the permutation. The second line contains $ n $ distinct integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the permutation itself. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 999 $ .

输出格式

For each test case print the number of iterations after which the permutation will become sorted in increasing order for the first time. If the given permutation is already sorted, print $ 0 $ .

输入输出样例

输入样例 #1

3
3
3 2 1
7
4 5 7 1 3 2 6
5
1 2 3 4 5

输出样例 #1

3
5
0

说明

In the first test case, the permutation will be changing as follows: - after the $ 1 $ -st iteration: $ [2, 3, 1] $ ; - after the $ 2 $ -nd iteration: $ [2, 1, 3] $ ; - after the $ 3 $ -rd iteration: $ [1, 2, 3] $ . In the second test case, the permutation will be changing as follows: - after the $ 1 $ -st iteration: $ [4, 5, 1, 7, 2, 3, 6] $ ; - after the $ 2 $ -nd iteration: $ [4, 1, 5, 2, 7, 3, 6] $ ; - after the $ 3 $ -rd iteration: $ [1, 4, 2, 5, 3, 7, 6] $ ; - after the $ 4 $ -th iteration: $ [1, 2, 4, 3, 5, 6, 7] $ ; - after the $ 5 $ -th iteration: $ [1, 2, 3, 4, 5, 6, 7] $ . In the third test case, the permutation is already sorted and the answer is $ 0 $ .