No.2029 Swap Min Max Min
タグ : / 解いたユーザー数 75
作問者 :
とりゐ
Problem Statement
You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ that is a permutation of $(1, 2, \dots, N)$.
First, you perform the operation of swapping adjacent $2$ elements of $A$ any number of times (possibly $0$ times).
Then, you create a sequence $B$ of length $N - 1$ defined by $B_i = \min(A_i, A_{i + 1})$ for each $i$ $(1 \leq i \leq N - 1)$.
Find the following $2$ values $X, Y$.
- The minimum possible value $X$ of the maximum value of $B$
- The minimum number of operations $Y$ required to achieve the above $X$
Constraints
- All inputs are integers
- $2 \leq N \leq 2 \times 10^5$
- $A$ is a permutation of $(1, 2, \dots, N)$
Input
The input is given from Standard Input in the following format.
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Output $X, Y$ in the following format. Print a newline at the end.
$X$ $Y$
Sample
Sample 1
Input
3 2 3 1
Output
1 1
Initially, the sequence is $A = (2, 3, 1)$. First, perform the operation $1$ time to get $(2, 3, 1) \rightarrow (2, 1, 3)$.
For this $A$, $B = (\min(2, 1), \min(1, 3)) = (1, 1)$, so the maximum value of $B$ is $1$.
No matter how you perform the operations, the maximum value of $B$ cannot be less than $1$, so $X = 1$. Also, the minimum number of operations is $1$, so $Y = 1$.
Sample 2
Input
5 1 2 3 4 5
Output
2 3
First, perform $3$ operations to get $(1, 2, 3, 4, 5) \rightarrow (1, 3, 2, 4, 5) \rightarrow (3, 1, 2, 4, 5) \rightarrow (3, 1, 4, 2, 5)$.
For this $A$, $B = (1, 1, 2, 2)$, so the maximum value of $B$ is $2$.
No matter how you perform the operations, the maximum value of $B$ cannot be less than $2$, so $X = 2$. Also, the minimum number of operations is $3$, so $Y = 3$.
Sample 3
Input
14 14 12 8 3 9 10 1 6 4 11 5 2 7 13
Output
7 9
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。