{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eYou are given the scores of several players in a\n competition. Your task is to create a ranklist of the players,\n sorted in decreasing order by score.\u003c/p\u003e\n\n \u003cp\u003eUnfortunately, the data structure used for the list of\n players supports only one operation, which moves a player from\n position \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e to position\n \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e without changing the\n relative order of other players. If \u003cspan class\u003d\"tex2jax_process\"\u003e$i \u0026gt; j$\u003c/span\u003e, the positions of players\n at positions between \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e\n and \u003cspan class\u003d\"tex2jax_process\"\u003e$i - 1$\u003c/span\u003e increase by\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, otherwise if\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i \u0026lt; j$\u003c/span\u003e the positions\n of players at positions between \u003cspan class\u003d\"tex2jax_process\"\u003e$i + 1$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e decrease by \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eThis operation takes \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e steps to locate the player to be\n moved, and \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e steps to\n locate the position where he or she is moved to, so the overall\n cost of moving a player from position \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e to position \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e is \u003cspan class\u003d\"tex2jax_process\"\u003e$i + j$\u003c/span\u003e. Here, positions are numbered\n starting with \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eDetermine a sequence of moves to create the ranklist such\n that the sum of the costs of the moves is minimized.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2\n \\le n \\le 1000$\u003c/span\u003e), the number of players. Each of the\n following \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines\n contains one non-negative integer \u003cspan class\u003d\"tex2jax_process\"\u003e$s_ i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le si \\le 1\\, 000\\, 000$\u003c/span\u003e), the\n scores of the players in the current order. You may assume that\n all scores are distinct.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eIn the first line of the output print the number of moves\n used to create the ranklist. The following lines should specify\n the moves in the order in which they are applied. Each move\n should be described by a line containing two integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e, which means that the player at\n position \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e is moved to\n position \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e. The numbers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e must be separated by a single\n space.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n20\n30\n5\n15\n10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2 1\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}