estie プログラミングコンテスト2024 (AtCoder Regular Contest 188)
E
Gravity Sort
AtCoder
未评级
原题
← D→
翻译中…

Problem Statement

翻译中…

There are $2N$ cells numbered from $1$ to $2N$ arranged vertically in a column with cell $1$ at the top. Each cell contains one ball. The weight of the ball in cell $i$ at time $t=0$ is $m_i$ for $i=1,2,\ldots,N$, and $0$ for $i=N+1,N+2,\ldots,2N$. Here, $(m_1, m_2, \ldots, m_N)$ is a permutation of the integers from $1$ to $N$.

翻译中…

In the following, we will refer to the ball of weight $i$ as ball $i$, and the cell number where each ball is located as the position of the ball.

翻译中…

From time $t=0$ onwards, every time the time advances by $1$, the heavier balls sink downward, and the lighter balls rise upward.

翻译中…

Formally, the positions of each ball at time $t=t_0+1$ are determined from their positions at time $t=t_0$ by the following procedure.

翻译中…
  • First, for $i=N,N-1,\ldots,2,1$ in this order, perform the following operation.
  • If the position of ball $i$ at $t=t_0+1$ has already been determined:
    • Do nothing.
    • If the position of ball $i$ at $t=t_0+1$ has not been determined:
    • If there exists a cell immediately below ball $i$ at $t=t_0$, and the ball in that cell (call it ball $j$) is lighter than ball $i$, set the positions of balls $i$ and $j$ at $t=t_0+1$ to be swapped from their positions at $t=t_0$.
      • Otherwise, set the position of ball $i$ at $t=t_0+1$ to be the same as at $t=t_0$.
  • Next, for all balls of weight $0$ whose positions at $t=t_0+1$ have not been determined at this point, set their positions at $t=t_0+1$ to be the same as at $t=t_0$.
翻译中…

It can be shown that at some time, the balls will be arranged from top to bottom in ascending order of weight, and their positions will no longer change. Find the time when this state is reached.

翻译中…

Constraints

翻译中…
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq m_i \leq N$
  • $m_i \neq m_j$ for $i \neq j$.
  • All input values are integers.
翻译中…

Input

翻译中…

The input is given from Standard Input in the following format:

翻译中…

N
m_1 m_2 \ldots m_N

翻译中…

Output

翻译中…

Print the answer as an integer.

翻译中…

样例

Input #1
3
2 3 1
Output #1
6
The movements from time $t=0$ to $t=1$ are determined as follows. (Refer to the diagram below if necessary.) > 1. For ball $3$, its position at $t=1$ has not yet been determined. The cell immediately below it contains ball $1$, and ball $3$ is heavier, so swap their positions for $t=1$. That is, set the position of ball $3$ to cell $3$, and ball $1$ to cell $2$. > 2. For ball $2$, its position at $t=1$ has not yet been determined. The cell immediately below it contains ball $3$, which is heavier than ball $2$, so set the position of ball $2$ at $t=1$ to be the same as at $t=0$. > 3. For ball $1$, its position at $t=1$ has already been determined in the earlier step. > 4. For balls of weight $0$, none of their positions at $t=1$ have been determined. Set their positions at $t=1$ to be the same as at $t=0$. Next, the movements from time $t=1$ to $t=2$ are determined as follows. > 1. For ball $3$, its position at $t=2$ has not yet been determined. The cell immediately below it contains ball $0$, and ball $3$ is heavier, so swap their positions for $t=2$. That is, set the position of ball $3$ to cell $4$, and ball $0$ (the one that was below ball $3$) to cell $3$. > 2. For ball $2$, its position at $t=2$ has not yet been determined. The cell immediately below it contains ball $1$, and ball $2$ is heavier, so swap their positions for $t=2$. That is, set the position of ball $2$ to cell $2$, and ball $1$ to cell $1$. > 3. For ball $1$, its position at $t=2$ has already been determined in the earlier step. > 4. For balls of weight $0$, the one that was at cell $4$ at $t=1$ has already had its position at $t=2$ determined in the earlier step. For the others, set their positions at $t=2$ to be the same as at $t=1$. Continuing to determine the positions of the balls in this way, at time $t=6$, the balls will be arranged from top to bottom as balls $0,0,0,1,2,3$, and their positions will no longer change. ![image](https://img.atcoder.jp/arc188/4e545d6825157293f80acafb7314f5d1.png)
Input #2
5
4 1 2 3 5
Output #2
9
Input #3
1
1
Output #3
1
题目信息
题号
arc188_e
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。