{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003eGiven \u003ci\u003eN\u003c/i\u003e numbers, \u003ci\u003eX\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003eX\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, ... , \u003ci\u003eX\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e, let us calculate the difference of every pair of numbers: ∣\u003ci\u003eX\u003csub\u003ei\u003c/sub\u003e \u003c/i\u003e-\u003ci\u003e X\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e∣ (1 ≤\u003ci\u003e i \u003c/i\u003e<\u003ci\u003e j \u003c/i\u003e≤\u003ci\u003e N\u003c/i\u003e). We can get \u003ci\u003eC(N,2)\u003c/i\u003e differences through this work, and now your task is to find the median of the differences as quickly as you can!\u003c/p\u003e\u003cp\u003eNote in this problem, the median is defined as the \u003ci\u003e(m/2)-th\u003c/i\u003e\u0026nbsp; smallest number if \u003ci\u003em\u003c/i\u003e,the amount of the differences, is even. For example, you have to find the third smallest one in the case of \u003ci\u003em \u003c/i\u003e\u003d 6.\u003c/p\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input consists of several test cases.\u003cbr\u003eIn each test case, \u003ci\u003eN\u003c/i\u003e will be given in the first line. Then \u003ci\u003eN\u003c/i\u003e numbers are given, representing \u003ci\u003eX\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003eX\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, ... , \u003ci\u003eX\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e, ( \u003ci\u003eX\u003csub\u003ei \u003c/sub\u003e\u003c/i\u003e≤ 1,000,000,000\u0026nbsp; 3 ≤ N ≤ 1,00,000 )\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output the median in a separate line.\u003c/p\u003e"}},{"title":"Sample","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\r\n1 3 2 4\r\n3\r\n1 10 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n8\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}