{"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThis problem is the most boring one you\u0027ve ever seen. \u003c/p\u003e\u003cp\u003eGiven a sequence of integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and a non-negative integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003c/span\u003e, our goal is to partition the sequence into two subsequences (not necessarily consist of continuous elements). Each element of the original sequence should be contained in exactly one of the result subsequences. Note, that one of the result subsequences can be empty.\u003c/p\u003e\u003cp\u003eLet\u0027s define function \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e(\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e on pairs of distinct elements (that is \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e ≠ \u003ci\u003ej\u003c/i\u003e\u003c/span\u003e) in the original sequence. If \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e are in the same subsequence in the current partition then \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e(\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e) \u003d \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e otherwise \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e(\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e) \u003d \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e + \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e + \u003ci\u003eh\u003c/i\u003e\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eConsider all possible values of the function \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e for some partition. We\u0027ll call the \u003cspan class\u003d\"tex-font-style-it\"\u003egoodness\u003c/span\u003e of this partiotion the difference between the maximum value of function \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e and the minimum value of function \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eYour task is to find a partition of the given sequence \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e that have the minimal possible goodness among all possible partitions.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e, 0 ≤ \u003ci\u003eh\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e8\u003c/sup\u003e)\u003c/span\u003e. In the second line there is a list of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e space-separated integers representing \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(0 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e8\u003c/sup\u003e)\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe first line of output should contain the required minimum goodness. \u003c/p\u003e\u003cp\u003eThe second line describes the optimal partition. You should print \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e whitespace-separated integers in the second line. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th integer is \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e if \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is in the first subsequence otherwise it should be \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIf there are several possible correct answers you are allowed to print any of them.\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\u003e3 2\n1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1 2 2 \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\u003e5 10\n0 1 0 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2 2 2 2 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\u003eIn the first sample the values of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e are as follows: \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e(1, 2) \u003d 1 + 2 + 2 \u003d 5\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e(1, 3) \u003d 1 + 3 + 2 \u003d 6\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e(2, 3) \u003d 2 + 3 \u003d 5\u003c/span\u003e. So the difference between maximum and minimum values of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e is \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the second sample the value of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003c/span\u003e is large, so it\u0027s better for one of the sub-sequences to be empty.\u003c/p\u003e"}}]}