{"problem":{"name":"[ROI 2018] Quick sort","description":{"content":"给一个包含 $n$ 个元素的排列 $[a_1,a_2,\\ldots,a_n]$。 定义操作 $S(l,r),$ 表示：将数列的片段 $[a_l,a_{l+1},\\ldots,a_r]$ 重排成 $[a_{l+1},a_{l+3},\\ldots,a_l,a_{l+2},\\ldots]$。 举个例子：$[2, 4, 1, 5, 3, 6, 7, 8]\\xrightarrow{S(2,6)} [2, 1","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9291"},"statements":[{"statement_type":"Markdown","content":"给一个包含 $n$ 个元素的排列 $[a_1,a_2,\\ldots,a_n]$。\n定义操作 $S(l,r),$ 表示：将数列的片段 $[a_l,a_{l+1},\\ldots,a_r]$ 重排成 $[a_{l+1},a_{l+3},\\ldots,a_l,a_{l+2},\\ldots]$。\n举个例子：$[2, 4, 1, 5, 3, 6, 7, 8]\\xrightarrow{S(2,6)} [2, 1, 3, 4, 5, 6, 7, 8]$， 其中子串 $[4, 1, 5, 3, 6]$ 被重排成了 $[1, 3, 4, 5, 6]$。\n给定一个排列，试求经过多少次操作能使排列变成递增顺序，并输出任意一组方案，$不$要求方案的操作次数最少，但要求操作次数 $\\leq 15000$。\n\n## Input\n\n第一行一个数 $n$。\n\n第二行 $n$ 个数，表示排列 $a$。\n\n## Output\n\n第一行一个整数 $k$，表示你的操作次数。 需要满足 $0 \\leq k \\leq 15000$。\n接下来 $k$ 行，你需要按照操作顺序描述你的操作。对于每一步操作，输出两个数 $L$, $R$，表示你对片段 $a_L,a_{L+1},\\ldots, a_R$ 执行了一次操作。 需满足 $1 \\leq L \\leq R \\le n$。\n注意，你**不**需要最小化。你只需保证 $0 \\le k \\leq 15000$ 即可。保证存在这样的 $k$。 \n\n[samples]\n\n## Background\n\n译自 [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T2. [Быстрая сортировка\n](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf)([Quick sort](http://codeforces.com/gym/102154/problem/C))。\n\n## Note\n\n此处设 $k_0$ 表示最小操作次数。\n\n对于所有数据，$1\\leq n\\leq 3000$，$0\\leq k_0\\leq 15000$，$1\\leq a_i\\leq n$，且 $a_i$ 互不相同。\n\n| 子任务编号 | $n$ | 特殊性质 |\n| :-----------: | :-----------: | :-----------: |\n| $1$ | $1 \\leq n \\leq 100$ | $k_0 = 1$ |\n| $2$ | $1 \\leq n \\leq 100$ | 无 |\n| $3$ | $1 \\leq n \\leq 1000$ | 无 |\n| $4$ | $1 \\leq n \\leq 3000$ | 无 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9291","tags":["2018","Special Judge","ROI（俄罗斯）"],"sample_group":[["5\n3 1 4 2 5","1\n1 5"],["8\n2 4 1 5 3 6 7 8","2\n2 6\n1 2\n"],["2\n2 1","3\n1 1\n2 2\n1 2"]],"created_at":"2026-03-03 11:09:25"}}