{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003e给定 \u003ci\u003eN\u003c/i\u003e 个数字,\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-\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)。通过这个过程,我们可以得到 \u003ci\u003eC(N,2)\u003c/i\u003e 个差值,现在你的任务是尽快找到这些差值的中位数!\u003c/p\u003e\u003cp\u003e注意,在这个问题中,如果差值的数量 \u003ci\u003em\u003c/i\u003e 是偶数,中位数被定义为第 \u003ci\u003e(m/2)-th\u003c/i\u003e\u0026nbsp; 小的数字。例如,当 \u003ci\u003em \u003c/i\u003e\u003d 6 时,你需要找到第三小的数字。\u003c/p\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入包括多个测试用例。\u003cbr\u003e在每个测试用例中,第一行给出 \u003ci\u003eN\u003c/i\u003e。然后给出 \u003ci\u003eN\u003c/i\u003e 个数字,表示 \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":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试用例,输出中位数。\u003c/p\u003e"}},{"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\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"}}]}