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 自动生成