交替算法 - المسألة

近年来，CPU 制造商发现要跟上摩尔定律（即每两年集成电路芯片上的晶体管数量翻倍）变得越来越困难。为了解决这个问题，制造商开始制造核心数量越来越多的 CPU。事实上，你刚刚购买了一台拥有惊人的 $n$ 个核心的 CPU！

CPUs. CC0 by Martijn Boer on Flickr

此外，你还有一个包含 $n + 1$ 个整数的数组 $a_0, a_1, \dots, a_n$，你需要对其进行排序。为了充分利用 CPU 的大量核心，你设计了一种并行排序算法，其中每个核心专门负责比较一对相邻的整数。只要数组不是非递减有序的，算法就会按轮次进行，轮次交替如下：

奇数轮（从第一轮开始）：第一个核心比较 $a_0$ 和 $a_1$，第三个核心比较 $a_2$ 和 $a_3$，第五个核心比较 $a_4$ 和 $a_5$，依此类推。如果一对被比较的元素顺序错误，对应的核心将交换它们的位置。如果 $n$ 是偶数，$a_n$ 将保持不变。
偶数轮：第二个核心比较 $a_1$ 和 $a_2$，第四个核心比较 $a_3$ 和 $a_4$，第六个核心比较 $a_5$ 和 $a_6$，依此类推。如果一对被比较的元素顺序错误，对应的核心将交换它们的位置。如果 $n$ 是奇数，$a_n$ 将保持不变；无论 $n$ 的奇偶性如何，$a_0$ 都将保持不变。

注意，在这两种类型的轮次中，某些核心可能会处于空闲状态。

在实现该算法之前，你决定进行一些分析。特别地，你注意到算法的时间复杂度并不取决于 $n$ 的值，而是取决于算法运行的轮数。给定数组的初始内容，确定并行排序算法在数组变得有序之前运行的轮数。

输入包含：

一行一个整数 $n$ ($1 \le n \le 4 \cdot 10^5$)，表示核心数量和数组的大小。
一行 $n + 1$ 个整数 $a_0, a_1, \dots, a_n$ ($0 \le a_i \le 10^9$，对于每个 $i$)，表示数组的初始内容。

输出并行排序算法在数组变为非递减有序之前运行的轮数。

3
8 13 4 10

5
13 12 14 10 14 12

2
2 2 1

QOJ.ac