Buy and Sell Stock - III Problem Statement

Given an array prices where the i^th element represents the price of a stock on the i^th day, your task is to determine the maximum profit that can be achieved at the end of the i^th day. You are allowed to complete at most two transactions.

Remember, you can only engage in one transaction at a time, meaning you must sell the stock before buying again. Also, it is not necessary to execute exactly two transactions.

Input:

The first line of input contains an integer 'T' indicating the number of test cases.

The first line of each test case contains a single integer 'N', the length of the array prices.

The second line of each test case consists of 'N' space-separated integers, each representing an element of the array prices.

Output:

For each test case, output the maximum profit that can be achieved by selling the stocks.

Example:

Given the input:

1
6
3 3 5 0 0 3 1 4

The expected output is:

6

Constraints:

• 1 <= T <= 50
• 1 <= N <= 10^4
• 0 <= prices[i] <= 10^9

Note

You do not need to print anything; it has already been taken care of.