405180: GYM101810 H Making Friends

Ali is trying to make his friends happier by matching them into pairs together. In the beginning, Ali has 2 × n friends standing in a row and numbered from 1 to 2 × n. Each friend i will be matched with the friend numbered (2 × n - i + 1).

Each friend i has a happiness level equal to h_i. The happiness level of a matched pair of friends i and (2 × n - i + 1) is equal to h_i + h_{2 × n - i + 1}.

Your task is to find the maximum happiness level of a pair among all matched pairs. Can you?

The first line contains an integer T (1 ≤ T ≤ 50) specifying the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 1000), giving that Ali has 2 × n friends. Then a line follows containing 2 × n integers h₁, ..., h_2 × n (1 ≤ h_i ≤ 1000), in which h_i represents the happiness level of the i^th friend.

For each test case, print a single line containing the maximum happiness level of a pair among all matched pairs.

1
3
2 4 5 6 7 8

11