Maximum Triplet Sum

You are given an array of integers. Your task is to select three distinct elements arr[i], arr[j], and arr[k] such that i < j < k and the sum arr[i] + arr[j] + arr[k] is maximized. The solution should read from standard input and output the result for each test case on standard output.

If there are fewer than 3 numbers in the array, consider it as an invalid case and output -1.

Note: Use the formula for the sum as \(S = a_{n-3} + a_{n-2} + a_{n-1}\) after sorting the array in non-decreasing order.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each test case consists of two lines:

• The first line contains an integer \(N\), the size of the array.
• The second line contains \(N\) space-separated integers.

outputFormat

For each test case, output the maximum sum of any triplet on a new line.

## sample

2
6
1 2 3 0 -1 8
5
-1 -3 -5 -7 -9

13
-9

</p>