問題一覧 > 通常問題

No.2029 Swap Min Max Min

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 73
作問者 : Shirotsume / テスター : 👑 ygussany とりゐ
4 ProblemId : 8185 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-05 23:32:36

問題文

(1,2,…,N)(1, 2, \dots, N) を並べ替えた長さ NN の数列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N) が与えられます。

あなたは初めに、 AA の 隣接する 22 要素を入れ替える操作を好きな回数（00 回でもよい）行います。

その後、各 ii (1≤i≤N−1)(1 \leq i \leq N - 1) について Bi=min⁡(Ai,Ai+1)B_i = \min(A_i, A_{i + 1}) で定める長さ N−1N - 1 の数列 BB を作ります。

以下に示す 22 つの値 X,YX, Y を求めてください。

  • BB の最大値として考えられる最小の値 XX
  • 上記の XX を達成するために必要な操作の最小回数 YY

制約

  • 入力は全て整数
  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • AA は (1,2,…,N)(1, 2, \dots, N) を並べ替えた数列

入力

入力は標準入力から以下の形式で与えられる。

NN
A1A_1 A2A_2 …\dots ANA_N

出力

X,YX, Y を以下の形式で出力せよ。最後に改行すること。

XX YY

サンプル

サンプル1
入力
3
2 3 1
出力
1 1

最初、数列 A=(2,3,1)A = (2, 3, 1) です。初めに、操作を 11 回行って (2,3,1)→(2,1,3)(2, 3, 1) \rightarrow (2, 1, 3) とします。

この AA に対して、 B=(min⁡(2,1),min⁡(1,3))=(1,1)B = (\min(2, 1), \min(1, 3)) = (1, 1) となるので、BB の最大値は 11 となります。

どのように操作をしても、 BB の最大値は 11 未満にはならないので、 X=1X = 1 です。また、操作回数の最小値は 11 回なので Y=1Y = 1 となります。

サンプル2
入力
5
1 2 3 4 5
出力
2 3

まず、33 回の操作を行って、 (1,2,3,4,5)→(1,3,2,4,5)→(3,1,2,4,5)→(3,1,4,2,5)(1, 2, 3, 4, 5) \rightarrow (1, 3, 2, 4, 5) \rightarrow (3, 1, 2, 4, 5) \rightarrow (3, 1, 4, 2, 5) とします。

この AA に対し、 B=(1,1,2,2)B = (1, 1, 2, 2) となるので、 BB の最大値は 22 となります。

どのように操作をしても、 BB の最大値は 22 未満にはならないので、 X=2X = 2 です。また、操作回数の最小値は 33 回なので Y=3Y = 3 となります。

サンプル3
入力
14
14 12 8 3 9 10 1 6 4 11 5 2 7 13
出力
7 9

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。