{"trustable":false,"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":"\u003cp\u003eYou are given the number of chips in a number of poker chips stacks. Your task is to sort the stacks in decreasing order.\u003c/p\u003e\n\u003cp\u003eUnfortunately, you are doing this after a long night of poker and thus your powers are limited to only one operation, which moves a stack from position \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e to position \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e without changing the relative order of the other stacks. If \u003cspan class\u003d\"tex2jax_process\"\u003e$i \u0026gt; j$\u003c/span\u003e, the positions of the stacks at positions between \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$i - 1$\u003c/span\u003e increase by \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, otherwise if \u003cspan class\u003d\"tex2jax_process\"\u003e$i \u0026lt; j$\u003c/span\u003e the positions of the stacks 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\u003cp\u003eThis operation takes \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e steps to locate the stack to be moved, and \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e steps to locate the position where the stack is moved to, so the overall cost of moving a stack 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 starting with \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eDetermine a sequence of moves to sort the stacks such that the sum of the costs of the moves is minimized.\u003c/p\u003e\n\u003ch2\u003eInput\u003c/h2\u003e\n\u003cp\u003eThe first line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\le n \\le 1000$\u003c/span\u003e), the number of stacks. Each of the following \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines 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 number of chips in each stack. You may assume that all stacks have different number of chips.\u003c/p\u003e\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003eIn the first line of the output print the number of moves used to sort the stacks. The following lines should specify the moves in the order in which they are applied. Each move should be described by a line containing two integers \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 stack at position \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e is moved to position \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e. The numbers \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 space.\u003c/p\u003e\n\u003ctable class\u003d\"sample\" summary\u003d\"sample data\"\u003e\n\u003ctbody\u003e\n\u003ctr\u003e\n\u003cth\u003eSample Input 1\u003c/th\u003e\n\u003cth\u003eSample Output 1\u003c/th\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e\n\u003cpre\u003e5\n20\n30\n5\n15\n10\n\u003c/pre\u003e\n\u003c/td\u003e\n\u003ctd\u003e\n\u003cpre\u003e2\n2 1\n3 5\n\u003c/pre\u003e\n\u003c/td\u003e\n\u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}