問題一覧 > 通常問題

No.2029 Swap Min Max Min

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 75
作問者 : Shirotsume / テスター : ygussany とりゐ
お気に入りにしたユーザー ProblemId : 8185 / 自分の提出
問題文最終更新日: 2022-08-05 23:32:36
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 355 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。