{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThere are $n$ buckets on the ground, where the $i$-th bucket contains $a_i$ stones. Each time one can perform one of the following two operations:\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003eRemove a stone from one of the non-empty buckets.\u003c/li\u003e\n \u003cli\u003eMove a stone from one of the buckets (must be non-empty) to any other bucket (can be empty).\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003eWhat\u0027s the minimum number of times one needs to perform the operations to make all the buckets contain the same number of stones?\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains an integer $n$ ($1 \\le n \\le 10^5$), indicating the number of buckets.\u003c/p\u003e\n\n\u003cp\u003eThe second line contains $n$ integers $a_1, a_2, \\dots, a_n$ ($0 \\le a_i \\le 10^9$), indicating the number of stones in the buckets.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing one integer, indicating the minimum number of times needed to make all the buckets contain the same number of stones.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\n3\n1 1 0\n4\n2 2 2 2\n3\n0 1 4\n1\n1000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n0\n3\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eFor the first sample test case, one can remove all the stones in the first two buckets.\u003c/p\u003e\n\n\u003cp\u003eFor the second sample test case, as all the buckets have already contained the same number of stones, no operation is needed.\u003c/p\u003e\n\n\u003cp\u003eFor the third sample test case, one can move 1 stone from the 3rd bucket to the 1st bucket and then remove 2 stones from the 3rd bucket.\u003c/p\u003e\n"}}]}