Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

$(1, 2, \dots, N)$ の順列 $P = (P_1, P_2, \dots, P_N)$ が与えられます。

長さ $N - 1$ の正の整数列 $T = (T_1, T_2, \dots, T_{N-1})$ に対して、値 $f(T)$ を次の手続きの戻り値として定義します。

手続き $f(T)$

  1. $t \leftarrow 0$。
  2. $P$ が昇順にソートされていない間、以下を繰り返す:
    • (a) $t \leftarrow t + 1$。
    • (b) $T_i \le t$ を満たすすべての添字 $i \in \{1, \dots, N - 1\}$ を昇順に並べた列を $S = (s_1, s_2, \dots, s_k)$ とする($s_1 < s_2 < \dots < s_k$)。
    • (c) $j = 1$ から $k$ まで順に以下を行う:
      • $i \leftarrow s_j$ とおく。その後、$P_i$ と $P_{i+1}$ を交換する。
    • (d) もし $t \ge 10^{100}$ ならば、$10^{100}$ を返す。
  3. $t$ を返す。

すべての正の整数列 $T$ にわたる $f(T)$ の最小値を求めてください。$f(T) < 10^{100}$ となる列 $T$ が存在することが保証されます。

入力

入力は以下の形式で与えられます。

N
P_1 P_2 ... P_N
  • 入力される値はすべて整数である。
  • $2 \le N \le 5000$.
  • $1 \le P_i \le N$.
  • $i \neq j$ のとき $P_i \neq P_j$。

出力

答えを出力してください。

入力例 1

4
4 2 1 3
2

入力例 2

20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
39

注記

1つ目の例では、$T = (2, 1, 2)$ とします。$t = 1$ のとき、$S = (2)$ より $P$ は $(4, 1, 2, 3)$ になります。$t = 2$ のとき、$S = (1, 2, 3)$ より順次交換を行うことで $P$ は $(4, 1, 2, 3) \to (1, 4, 2, 3) \to (1, 2, 4, 3) \to (1, 2, 3, 4)$ と変化します。したがって $f(T) = 2$ です。$f(T) < 2$ となる $T$ は存在しないため、答えは $2$ です。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.