{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eTakahashi\u0027s and Aoki\u0027s garden is covered with \u003cvar\u003e\\(N\\)\u003c/var\u003e weeds, called Weed \u003cvar\u003e\\(1\\)\u003c/var\u003e, Weed \u003cvar\u003e\\(2\\)\u003c/var\u003e, \u003cvar\u003e\\(\\ldots\\)\u003c/var\u003e, Weed \u003cvar\u003e\\(N\\)\u003c/var\u003e. The height of Weed \u003cvar\u003e\\(i\\)\u003c/var\u003e is \u003cvar\u003e\\(A_i\\)\u003c/var\u003e.\r\nTakahashi and Aoki have decided to pull these weeds, as follows:\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eFirst, Aoki will choose at most \u003cvar\u003e\\(K\\)\u003c/var\u003e weeds and pull them.\u003c/li\u003e\r\n\u003cli\u003eThen, Takahashi will repeat the following operation until all weeds are pulled.\u003cul\u003e\r\n\u003cli\u003eLet \u003cvar\u003e\\(H\\)\u003c/var\u003e be the height of the tallest remaining weeds. Pull all weeds with heights above \u003cvar\u003e\\(\\frac{H}{2}\\)\u003c/var\u003e at once.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eAoki wants to minimize the number of operations done by Takahashi. Also, he wants to minimize it by pulling the minimum number of weeds needed.\r\nFind the number of operations done by Takahashi and the number of weeds Aoki pulls in this case.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Constraints","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq N \\leq 2\\times 10^5\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(0 \\leq K \\leq N\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq A_i \\leq 10^9\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003eAll values in input are integers.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Input","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eInput is given from Standard Input in the following format:\u003c/p\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(N\\)\u003c/var\u003e \u003cvar\u003e\\(K\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(A_1\\)\u003c/var\u003e \u003cvar\u003e\\(A_2\\)\u003c/var\u003e \u003cvar\u003e\\(\\ldots\\)\u003c/var\u003e \u003cvar\u003e\\(A_N\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Output","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003ePrint the number of operations Takahashi will do and the number of weeds Aoki will pull, in this order, with a space in between.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 1","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\u003e4 1\r\n2 3 4 9\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cp\u003eFor example, assume that Aoki chooses Weed \u003cvar\u003e\\(4\\)\u003c/var\u003e, with height \u003cvar\u003e\\(9\\)\u003c/var\u003e, and pulls it. Then, the tallest remaining weed is Weed \u003cvar\u003e\\(3\\)\u003c/var\u003e, with height \u003cvar\u003e\\(4\\)\u003c/var\u003e.\r\nWe have \u003cvar\u003e\\(\\frac{4}{2}\u003d2\\)\u003c/var\u003e, and Takahashi will pull Weed \u003cvar\u003e\\(2\\)\u003c/var\u003e and \u003cvar\u003e\\(3\\)\u003c/var\u003e in the first operation, since \u003cvar\u003e\\(2\u0026lt;3\\)\u003c/var\u003e and \u003cvar\u003e\\(2\u0026lt;4\\)\u003c/var\u003e. Then, he will pull Weed \u003cvar\u003e\\(1\\)\u003c/var\u003e in the second operation, completing his work in two operations.\r\nOn the other hand, he will not complete his work in one operation, no matter which one weed Aoki chooses.\u003c/p\u003e\r\n\u003cp\u003eAlso, if Aoki pulls no weed, Takahashi will have to do three operations, so Aoki must pull at least one weed to minimize the number of operations done by Takahashi.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 2","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 3\r\n2 3 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cp\u003eIf Aoki pulls all weeds, Takahashi has to do zero operations, which is obviously the smallest number possible.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 3","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\u003e9 8\r\n137 55 56 60 27 28 133 56 55\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\u003c/section\u003e\r\n"}}]}