#P9893. [ICPC 2018 Qingdao R] Soldier Game

[ICPC 2018 Qingdao R] Soldier Game

题目描述

DreamGrid and BaoBao are playing a game. There are nn soldiers in the game, numbered from 11 to nn. The ii-th soldier has a power value of aia_i. DreamGrid and BaoBao are going to divide the soldiers into several teams according to the rules below:

  • A team must consist of 1 or 2 soldiers.
  • Every soldier must belong to exactly 1 team.
  • If a team consists of two soldiers (let's say they are the ii-th and the jj-th soldier), there must be ij=1|i - j| = 1.

The power value of a team is defined as the sum of the team members' 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.

输入格式

There are multiple test cases. The first line of the input contains an integer TT, indicating the number of test cases. For each test case:

The first line contains an integer nn (1n1051 \le n \le 10^5), indicating the number of soldiers.

The second line contains nn integers a1,a2,...,ana_1, a_2, ... , a_n (109ai109-10^9 \le a_i \le 10^9), where aia_i indicates the power value of the ii-th soldier.

It's guaranteed that the sum of nn in all test cases will not exceed 10610^6.

输出格式

For 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.

3
5
-1 4 2 1 1
4
1 3 2 4
1
7
1
2
0

提示

We now explain the first sample test case. All possible divisions are listed below.

Division Difference Division Difference
[-1], [4], [2], [1], [1] 4 - (-1) = 5 [-1, 4], [2], [1], [1] 3 - 1 = 2
[-1], [4], [2], [1, 1] [-1], [4, 2], [1, 1] 6 - (-1) = 7
[-1], [4], [2, 1], [1] [-1, 4], [2], [1, 1] 3 - 2 = 1
[-1], [4, 2], [1], [1] 6 - (-1) = 7 [-1, 4], [2, 1], [1] 3 - 1 = 2

So the answer is min(5,5,5,7,2,7,1,2)=1\min(5, 5, 5, 7, 2, 7, 1, 2) = 1.