题目描述

给定一个长度为 $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-2)$。否则执行 $f(2),f(4),\ldots,f(n-1)$。

请求出：多少次操作后，这个数列是递增的的？

输入格式

包含 $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$ 为奇数。

样例

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

3
5
0