{"problem":{"name":"[LSOT-2] 基于二分查找与插入的快速排序","description":{"content":"给定一个排列 $p$。每次可以选择一个数 $p_i$，你需要找到最小的 $j$，使得 $j>i$ 且 $p_j>p_i$，并将 $p_i$ 插入到 $p_j$ 前面。你需要最小化使得 $p_i=i$ 的操作次数。 若不存在这样的 $j$，则无法进行操作。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10155"},"statements":[{"statement_type":"Markdown","content":"给定一个排列 $p$。每次可以选择一个数 $p_i$，你需要找到最小的 $j$，使得 $j>i$ 且 $p_j>p_i$，并将 $p_i$ 插入到 $p_j$ 前面。你需要最小化使得 $p_i=i$ 的操作次数。\n\n若不存在这样的 $j$，则无法进行操作。\n\n## Input\n\n第一行一个整数 $n$，表示排列的长度。\n\n接下来一行 $n$ 个整数描述排列 $p$，第 $i$ 个数为 $p_i$。\n\n## Output\n\n一行一个整数表示最小的操作次数。若无法完成排序输出 $-1$。\n\n[samples]\n\n## Background\n\n小 H 不会排序，但是会二分！\n\n于是他创造了一个基于二分查找与插入的快速排序。\n\n本题存在可带修做法，因为这题是这场考试的签到题所以良心出题人没有加上。\n\n## Note\n\n**「本题采用捆绑测试」**\n\n- $\\texttt{Subtask 1(20pts)：}n\\le10$。\n- $\\texttt{Subtask 2(20pts)：}$保证 $p_i=n-i+1$。\n- $\\texttt{Subtask 3(20pts)：}n\\le1000$。\n- $\\texttt{Subtask 4(40pts)：}$无特殊性质。\n\n对于全部的数据，$1\\le n\\le2\\times 10^6$，$p$ 是一个 $1$ 到 $n$ 的排列。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10155","tags":["贪心"],"sample_group":[["5\n3 1 4 2 5","2"]],"created_at":"2026-03-03 11:09:25"}}