{"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\u003eDreamGrid and BaoBao are playing a game. There are $n$ soldiers in the game, numbered from $1$ to $n$. The $i$-th soldier has a power value of $a_i$. DreamGrid and BaoBao are going to divide the soldiers into several teams according to the rules below:\r\n\r\n\u003c/p\u003e\u003cul\u003e\r\n \u003cli\u003eA team must consist of 1 or 2 soldiers.\u003c/li\u003e\r\n \u003cli\u003eEvery soldier must belong to exactly 1 team.\u003c/li\u003e\r\n \u003cli\u003eIf a team consists of two soldiers (let\u0027s say they are the $i$-th and the $j$-th soldier), there must be $|i - j| \u003d 1$.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003cp\u003eThe power value of a team is defined as the sum of the team members\u0027 power values. For the sake of fairness, they want to minimize the difference between the maximum team power value and the minimum team power value after the division. You are asked to find the minimum difference.\u003c/p\u003e\r\n\r\n\u003ch4\u003eInput\u003c/h4\u003e\r\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\r\n\r\n\u003cp\u003eThe first line contains an integer $n$ ($1 \\le n \\le 10^5$), indicating the number of soldiers.\u003c/p\u003e\r\n\r\n\u003cp\u003eThe second line contains $n$ integers $a_1, a_2, \\dots, a_n$ ($-10^9 \\le a_i \\le 10^9$), where $a_i$ indicates the power value of the $i$-th soldier.\u003c/p\u003e\r\n\r\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n$ in all test cases will not exceed $10^6$.\u003c/p\u003e\r\n\r\n\u003ch4\u003eOutput\u003c/h4\u003e\r\n\u003cp\u003eFor each test case output one line containing one integer, indicating the minimum difference between the maximum team power value and the minimum team power value.\u003c/p\u003e\r\n\r\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\u003e3\r\n5\r\n-1 4 2 1 1\r\n4\r\n1 3 2 4\r\n1\r\n7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n2\r\n0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003ch4\u003eHint\u003c/h4\u003e\r\n\u003cp\u003eWe now explain the first sample test case. All possible divisions are listed below.\u003c/p\u003e\r\n\r\n\u003ccenter\u003e\r\n\u003ctable id\u003d\"problem-table\" style\u003d\"border-collapse: collapse; text-align: center;\" align\u003d\"center\"\u003e\r\n \u003cthead\u003e\r\n \u003ctr\u003e\u003cth\u003eDivision\u003c/th\u003e\u003cth\u003eDifference\u003c/th\u003e\u003cth\u003eDivision\u003c/th\u003e\u003cth\u003eDifference\u003c/th\u003e\u003c/tr\u003e\r\n \u003c/thead\u003e\r\n \u003ctbody\u003e\r\n \u003ctr\u003e\u003ctd\u003e[-1], [4], [2], [1], [1]\u003c/td\u003e\u003ctd\u003e4 - (-1) \u003d 5\u003c/td\u003e\u003ctd\u003e[-1, 4], [2], [1], [1]\u003c/td\u003e\u003ctd\u003e3 - 1 \u003d 2\u003c/td\u003e\u003c/tr\u003e\r\n \u003ctr\u003e\u003ctd\u003e[-1], [4], [2], [1, 1]\u003c/td\u003e\u003ctd\u003e4 - (-1) \u003d 5\u003c/td\u003e\u003ctd\u003e[-1], [4, 2], [1, 1]\u003c/td\u003e\u003ctd\u003e6 - (-1) \u003d 7\u003c/td\u003e\u003c/tr\u003e\r\n \u003ctr\u003e\u003ctd\u003e[-1], [4], [2, 1], [1]\u003c/td\u003e\u003ctd\u003e4 - (-1) \u003d 5\u003c/td\u003e\u003ctd\u003e[-1, 4], [2], [1, 1]\u003c/td\u003e\u003ctd\u003e3 - 2 \u003d 1\u003c/td\u003e\u003c/tr\u003e\r\n \u003ctr\u003e\u003ctd\u003e[-1], [4, 2], [1], [1]\u003c/td\u003e\u003ctd\u003e6 - (-1) \u003d 7\u003c/td\u003e\u003ctd\u003e[-1, 4], [2, 1], [1]\u003c/td\u003e\u003ctd\u003e3 - 1 \u003d 2\u003c/td\u003e\u003c/tr\u003e\r\n \u003c/tbody\u003e\r\n\u003c/table\u003e\r\n\u003c/center\u003e\r\n\r\n\u003cp\u003eSo the answer is $\\min(5, 5, 5, 7, 2, 7, 1, 2) \u003d 1$.\u003c/p\u003e\r\n\r\n\u003cstyle type\u003d\"text/css\"\u003e\r\n#problem-table \u003e thead \u003e tr \u003e th, #problem-table \u003e tbody \u003e tr \u003e td\r\n{\r\n padding: 3px 5px;\r\n border: 1px solid black;\r\n}\r\n\u003c/style\u003e\r\n"}}]}