P17049 [NWERC 2022] 交替算法 / Alternating Algorithm

译自 [Northwestern Europe Regional Contest (NWERC) 2022](https://2022.nwerc.eu) Problem A。 原题许可协议为 CC BY-SA。

近年来，CPU 制造商发现，要继续跟上摩尔定律中“集成电路芯片上的晶体管数量每两年翻一番”的速度，已经越来越困难。为了解决这个问题，制造商转而开始制造核心数量越来越多的 CPU。事实上，你刚刚买到了一块拥有惊人数量 $n$ 个核心的 CPU！ 巧的是，你还有一个包含 $n+1$ 个整数的数组 $a_0,a_1,\ldots,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 \leq n \leq 4\cdot 10^5$），表示核心数量以及数组大小参数。 - 一行 $n+1$ 个整数 $a_0,a_1,\ldots,a_n$（对于每个 $i$，$0 \leq a_i \leq 10^9$），表示数组的初始内容。

输出这个并行排序算法在数组按非降序排好序之前运行的轮数。

【数据规模与约定】 对于所有数据，满足 $1 \leq n \leq 4\cdot 10^5$；$0 \leq a_i \leq 10^9$。