AT_arc188_e [ARC188E] Gravity Sort
题目描述
在一个从上到下排成一列的 $2N$ 个格子中，每个格子都有一个编号，从 $1$ 到 $2N$。每个格子里放着一个球。在时刻 $t=0$，编号 $i$ 的格子中球的重量为：若 $i=1,2,\ldots,N$，则为 $m_i$；若 $i=N+1,N+2,\ldots,2N$，则为 $0$。这里，$(m_1, m_2, \ldots, m_N)$ 是 $1$ 到 $N$ 的一个排列。
在接下来的时间里，重球会下沉，轻球会上浮。具体来说，给定时刻 $t=t_0$，我们按照以下步骤确定时刻 $t=t_0+1$ 的球位置：
1. 从 $N$ 至 $1$ 依次处理：
- 如果球 $i$ 在时刻 $t=t_0+1$ 的位置已确定，**则不进行操作**。
- 如果球 $i$ 在时刻 $t=t_0+1$ 的位置尚未确定：
- 若其下方的格子存在于时刻 $t=t_0$，且该位置球的重量小于球 $i$，则**交换两个位置**。
- 否则，**保持球 $i$ 在时刻 $t=t_0+1$ 的位置不变**。
2. 对于所有尚未确定位置的重量为 $0$ 的球，**保持其位置不变**。
最终，在某一时刻，球将按由上到下轻重顺序排列，且此后位置不再变化。请计算实现这一状态所需的最小时刻。
输入格式
输入由以下格式给出：
> $N$ $m_1$ $m_2$ $\ldots$ $m_N$
输出格式
输出一个整数表示达到最终状态的时刻。
说明/提示
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq m_i \leq N$
- 对于 $i \neq j$ 有 $m_i \neq m_j$
**样例解释**
从时刻 $t=0$ 开始，球按指令逐步调整位置，最终在时刻 $t=6$ 得到从上到下为 $0, 0, 0, 1, 2, 3$ 的位置排列，并保持不变。可据图表进行理解：
**本翻译由 AI 自动生成**