Visuals can be deceptive, and so can be the titles of the contest, but not every time you'll be asked tough questions in an EASY contest.

In this problem, you will be given an array of integers and you need to tell the cost of the cheapest possible subarray of length at least two.

A subarray is the sequence of consecutive elements of the array and the cost of a subarray is the sum of minimum and the maximum value in the subarray.

Note: In an array of length \(n\), there are \(\frac{n(n-1)}{2}\) subarrays whose length is atleast 2.

Constraints:

\(1 \le t \le 10\)
\(2 \le n \le 2 \times 10^4\)
\(1 \le a_i \le 2 \times 10^4\)

Input Format:

The first line contains a single integer \(t\) denoting the number of test cases.

The first line of each test case contains \(n\) i.e the number of elements in the array. Next lines contains \(n\) space-separated integers \(a_i\)

Output Format:

Print \(t\) lines each containing a single integer. \(i^{th}\) integer denotes the cost of the cheapest subarray for the \(i^{th}\) array.