{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe scientists invented the new UL-2018 processor that is able to quickly process arrays in some special way. A key feature of its architecture is the \u003cspan class\u003d\"tex-font-style-it\"\u003eseparation\u003c/span\u003e operation of a segment of the array.\u003c/p\u003e\u003cp\u003eConsider an array $$$[a_1, a_2, \\ldots, a_n]$$$. The separation operation is characterized by two integers $$$L$$$ and $$$R$$$. Let $$$S(L, R)$$$ denote the operation of the segment $$$[a_L, a_{L+1}, \\ldots, a_R]$$$. Executing the $$$S(L, R)$$$ operation reorders the elements in this segment as follows. First, the elements $$$a_{L+1}, a_{L+3}, a_{L+5}, \\ldots$$$ are taken, that is elements $$$a_i$$$ that $$$i - L$$$ is odd. Their relative order remains unchanged. Then, the elements $$$a_L, a_{L+2}, a_{L+4}, \\ldots$$$ are taken ($$$a_i$$$ that $$$i - L$$$ is even). These retain the relative order too.\u003c/p\u003e\u003cp\u003eFor example, consider the array $$$[2, 4, 1, 5, 3, 6, 7, 8]$$$. Applying the operation $$$S(2, 6)$$$ changes the segment $$$[4, 1, 5, 3, 6]$$$ into $$$[1, 3, 4, 5, 6]$$$, so the entire array becomes $$$[2, 1, 3, 4, 5, 6, 7, 8]$$$. \u003c/p\u003e\u003cp\u003eTo demonstrate the capabilities of the new processor, the scientists decided to use separation operations to sort an array of distinct numbers. You will be given an array of size $$$n$$$ ($$$1 \\le n \\le 3\\,000$$$) with distinct numbers from $$$1$$$ to $$$n$$$. You must sort it in ascending order using no more than $$$15\\,000$$$ separation operations.\u003c/p\u003e\u003cp\u003eFor example, the mentioned array $$$[2, 4, 1, 5, 3, 6, 7, 8]$$$ can be sorted in two separation operations. First, apply $$$S(2, 6)$$$ to get $$$[2, 1, 3, 4, 5, 6, 7, 8]$$$, and then the operation $$$S(1, 2)$$$ makes the array sorted increasingly: $$$[1, 2, 3, 4, 5, 6, 7, 8]$$$.\u003c/p\u003e\u003cp\u003eYour task is to write a program that for a given array determines the sequence of at most $$$15\\,000$$$ separation operations, after which the specified array will be sorted in ascending order. It isn\u0027t necessary to minimize the number of operations performed (just use at most $$$15\\,000$$$).\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains an integer $$$n$$$\u0026nbsp;— the number of elements in the given array ($$$1 \\le n \\le 3000$$$).\u003c/p\u003e\u003cp\u003eThe second line contains $$$n$$$ distinct integers $$$a_1, a_2, \\ldots, a_n$$$\u0026nbsp;— the elements of the given array ($$$1 \\le a_i \\le n$$$, all $$$a_i$$$ are different). \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the output should contain an integer $$$k$$$\u0026nbsp;— the number of separation operations performed ($$$0 \\le k \\le 15\\,000$$$). \u003c/p\u003e\u003cp\u003eIn the following $$$k$$$ lines, you should print the description of the operations, in the order they are executed. Each operation is described by two integers $$$L$$$ and $$$R$$$\u0026nbsp;— the beginning and the end of the segment to which the separation operation should be applied ($$$1 \\le L \\le R \\le n$$$).\u003c/p\u003e\u003cp\u003eNote that you don\u0027t have to minimize the number $$$k$$$. You can output any sequence of separation operations that contains at most $$$15\\,000$$$ operations and sorts the given array in ascending order. It is guaranteed that at least one such sequence exists.\u003c/p\u003e"}},{"title":"Scoring","value":{"format":"HTML","content":"\u003cp\u003e$$$$$$ \\begin{array}{|c|c|c|c|} \\hline \\text{Subtask} \u0026amp; \\text{Points} \u0026amp; \\text{Constraints} \u0026amp; \\text{Dependencies} \\\\ \\hline 1 \u0026amp; 20 \u0026amp; n \\le 100; \\ \\text{there is a solution with } k \u003d 1 \u0026amp; \\\\ \\hline 2 \u0026amp; 30 \u0026amp; n \\le 100 \u0026amp; 0, 1 \\\\ \\hline 3 \u0026amp; 30 \u0026amp; n \\le 1\\,000 \u0026amp; 0-2 \\\\ \\hline 4 \u0026amp; 20 \u0026amp; n \\le 3\\,000 \u0026amp; 0-3 \\\\ \\hline \\end{array}$$$$$$\u003c/p\u003e\u003cp\u003eYou will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\n3 1 4 2 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e8\n2 4 1 5 3 6 7 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2 6\n1 2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e2\n2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 1\n2 2\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe second sample test is analyzed in detail in the problem statement.\u003c/p\u003e\u003cp\u003eIn the third sample test, there is a solution with a single separation operation, but since you don\u0027t have to minimize the number of operations, the provided output is also correct.\u003c/p\u003e"}}]}