No.1834 1D Gravity
riano
cn_449
ygussanyProblem Statement
Riano is playing with a model of a strange universe in which stars are lined up on a $1$-dimensional number line.
In this model, at time $t=0$, stars with masses $m_1,m_2,...,m_N$ exist at $x=1,2,...,N$ respectively on an infinitely long number line.
Here, $m_1,m_2,...,m_N$ is a permutation of $1,2,...,N$.
Also, each time the time advances by $1$, all stars simultaneously "move to whichever of the two adjacent coordinates has the heavier star", and this repeats.
Formally, the positions of the stars from $t=1$ onward are determined by the following rule:
- When a star is at coordinate $x_0$ at time $t_0$, let $M_-$ be the maximum mass of the stars at $x_0-1$ at that time, and let $M_+$ be the maximum mass of the stars at $x_0+1$ at that time. If no star exists at the respective coordinate, the value is regarded as $0$. The position of this star at time $t_0+1$ is coordinate $x_0-1$ if $M_->M_+$, and coordinate $x_0+1$ if $M_-< M_+$.
After a sufficient amount of time, the stars become divided into several groups, each alternating back and forth between $2$ adjacent coordinates. Riano has named this state the "final state" and is very interested in it. On behalf of Riano, find the time at which the final state is reached and the number of groups of stars existing in the final state.
Formally, it is possible to choose an integer $t_\mathrm{end}$ such that the following proposition is true for all stars:
- By choosing an appropriate integer $x_\mathrm{end}$, this star is always at $x=x_\mathrm{end}$ or $x=x_\mathrm{end}+1$ for $t\geq t_\mathrm{end}$.
[Reference figure of the movement of the stars]
Input
$N$ $m_1$ $m_2$ $...$ $m_N$
- $2\leq N \leq 2\times 10^5$
- $1\leq m_i \leq N$ $(1\leq i \leq N)$
- $m_i\neq m_j$ $(i\neq j)$
- All inputs are integers.
Output
Output, as integers separated by a space, "the time at which the final state is reached" and "the number of groups of stars in the final state", in this order. Print a newline at the end.
Sample
Sample 1
Input
5 3 4 1 5 2
Output
1 2
This input corresponds to Figure $1$ of the reference figure in the problem statement.
The positions of the stars change as shown in the figure, and since the state at $t=3$ is equal to the state at $t=1$, from then on
the group consisting of stars $1,2,5$ goes back and forth between $x=4,5$, and the group of stars $3,4$ goes back and forth between $x=1,2$.
That is, from $t=1$ onward, the stars can be said to be divided into $2$ groups, each alternating between $2$ coordinates.
Therefore, "the time at which the final state is reached" is $1$, and "the number of groups of stars in the final state" is $2$.
Formally, the coordinates of each star from $t_\mathrm{end}=1$ onward satisfy the required proposition by taking $x_\mathrm{end}=1$ for stars $3,4$ and $x_\mathrm{end}=4$ for stars $1,2,5$.
Note that, as shown in the figure, even when multiple stars exist at the same coordinate, they do not merge or the like; each is evaluated only by its individual mass.
Sample 2
Input
5 3 4 2 5 1
Output
2 1
This input corresponds to Figure $2$ of the reference figure in the problem statement. As shown in the reference figure, in this case all stars go back and forth between $x=2,3$ from $t_\mathrm{end}=2$ onward, so "the time at which the final state is reached" is $2$, and "the number of groups of stars in the final state" is $1$.
Sample 3
Input
9 3 2 8 5 1 7 9 6 4
Output
2 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。