← 返回题目列表

Codeforces · 1558/F

F. 奇怪的排序

中文机器翻译题面 查看原题

你有一个排列:一个数组 $$$a = [a_1, a_2, \ldots, a_n]$$$,由从 $$$1$$$ 到 $$$n$$$ 的不同整数组成。排列 $$$n$$$ 的长度是奇数。

考虑以下按升序对排列进行排序的算法。

该算法的辅助过程 $$$f(i)$$$ 采用单个参数 $$$i$$$ ($$$1 \le i \le n-1$$$) 并执行以下操作。如果 $$$a_i > a_{i+1}$$$,则交换 $$$a_i$$$ 和 $$$a_{i+1}$$$ 的值。否则,排列不会改变。

该算法由迭代组成,以 $$$1$$$ 开头的连续整数进行编号。在第 $$$i$$$ 次迭代中,算法执行以下操作:

- 如果 $$$i$$$ 为奇数,则调用 $$$f(1), f(3), \ldots, f(n - 2)$$$;
- 如果 $$$i$$$ 是偶数,则调用 $$$f(2), f(4), \ldots, f(n - 1)$$$。

可以证明,经过有限次数的迭代后,排列将按升序排序。

经过多少次迭代后,这种情况第一次会发生?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$($$$3 \le n \le 2 \cdot 10^5 - 1$$$;$$$n$$$ 为奇数)— 排列的长度。

第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - 排列本身。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5 - 1$$$。

输出

对于每个测试用例,打印迭代次数,之后排列将首次按升序排序。

如果给定的排列已经排序,则打印 $$$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

注意

在第一个测试用例中,排列将发生如下变化:

- 在 $$$1$$$-st 迭代之后:$$$[2, 3, 1]$$$;
- 在 $$$2$$$-nd 迭代之后:$$$[2, 1, 3]$$$;
- 在 $$$3$$$-rd 迭代之后:$$$[1, 2, 3]$$$。

在第二个测试用例中,排列将发生如下变化:

- 在 $$$1$$$-st 迭代之后:$$$[4, 5, 1, 7, 2, 3, 6]$$$;
- 在 $$$2$$$-nd 迭代之后:$$$[4, 1, 5, 2, 7, 3, 6]$$$;
- 在 $$$3$$$-rd 次迭代之后:$$$[1, 4, 2, 5, 3, 7, 6]$$$;
- 第 $$$4$$$ 次迭代之后:$$$[1, 2, 4, 3, 5, 6, 7]$$$;
- 第 $$$5$$$ 次迭代之后:$$$[1, 2, 3, 4, 5, 6, 7]$$$。

在第三个测试用例中,排列已经排序,答案是 $$$0$$$。