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.
样例
3
2 3 1
6
5
4 1 2 3 5
9
1
1
1
题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。