← 返回题目列表

AtCoder · arc188_e

E. 重力排序

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

分数: 1000 点

问题陈述

有 2N 单元格编号为 1 to 2N 垂直排列在带有单元格的列中 1 在顶部。每个单元格包含一个球。球在细胞内的重量 i 时间 t=0 is m_i 为 i=1,2,\ldots,N,和 0 为 i=N+1,N+2,\ldots,2N。在这里, (m_1, m_2, \ldots, m_N) 是以下整数的排列 1 to N.

下面我们将提到重量球 i 作为球 i,每个球所在的单元格编号作为球的位置。

从时间 t=0 开始,时间每前进 1,较重的球向下沉,较轻的球向上上升。

正式来说,每个球当时的位置 t=t_0+1 由他们当时的位置确定 t=t_0 通过以下过程。

  • 首先,对于 i=N,N-1,\ldots,2,1 按此顺序执行以下操作。
    • 如果球的位置 i at t=t_0+1 已经确定:
      • 什么也不做。
    • 如果球的位置 i at t=t_0+1 尚未确定:
      • 如果球正下方存在一个单元格 i at t=t_0,以及该单元格中的球(称之为球 j) 比球轻 i, 设置球的位置 i 和 j at t=t_0+1 的位置将被交换 t=t_0.
      • 否则, 设置球的位置 i at t=t_0+1 与以下相同 t=t_0.
  • 接下来,对于所有重量球 0 其职位位于 t=t_0+1 目前尚未确定, 将其位置设置为 t=t_0+1 与以下相同 t=t_0.

可以看出,在某个时刻,小球会按照重量从小到大的顺序从上到下排列,并且它们的位置不再改变。求达到该状态的时间。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq m_i \leq N
  • m_i \neq m_j 为 i \neq j.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
m_1 m_2 \ldots m_N

输出

将答案打印为整数。


示例输入 1

3
2 3 1

示例输出 1

6

时间的变化 t=0 to t=1 确定如下。 (如有需要,请参考下图。)

  1. 对于球 3,其位置为 t=1 尚未确定。紧邻其下方的单元格包含球 1和球 3 更重,所以交换它们的位置 t=1。即设定球的位置 3 到单元格 3和球 1 到单元格 2.
  2. 对于球 2,其位置为 t=1 尚未确定。紧邻其下方的单元格包含球 3,比球重 2,所以设置球的位置 2 at t=1 与以下相同 t=0.
  3. 对于球 1,其位置为 t=1 已在前面的步骤中确定。
  4. 对于重球 0,他们的位置都不在 t=1 已确定。将他们的位置设置为 t=1 与以下相同 t=0.

接下来,时间的动向 t=1 to t=2 确定如下。

  1. 对于球 3,其位置为 t=2 尚未确定。紧邻其下方的单元格包含球 0和球 3 更重,所以交换它们的位置 t=2。即设定球的位置 3 到单元格 4和球 0 (球下方的那个 3) 到单元格 3.
  2. 对于球 2,其位置为 t=2 尚未确定。紧邻其下方的单元格包含球 1和球 2 更重,所以交换它们的位置 t=2。即设定球的位置 2 到单元格 2和球 1 到单元格 1.
  3. 对于球 1,其位置为 t=2 已在前面的步骤中确定。
  4. 对于重球 0,位于牢房的那个 4 at t=1 已在 t=2 在前面的步骤中确定。对于其他人,将其位置设置为 t=2 与以下相同 t=1.

继续以这种方式确定球的位置,此时 t=6,球将从上到下排列为球 0,0,0,1,2,3,并且他们的位置将不再改变。


示例输入 2

5
4 1 2 3 5

示例输出 2

9

示例输入 3

1
1

示例输出 3

1