Maximum Profit with at Most Two Stock Transactions

You are given an array prices where prices[i] represents the price of a stock on the i-th day. Your task is to compute the maximum profit that can be achieved with at most two transactions. Note that you may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

A transaction is defined as the act of buying and then selling one share of the stock. If no profit can be achieved, return 0.

The problem can be formally stated as:

\( \text{Given an array } prices \text{, find } f(prices) = \max\{ p : \text{profit from at most 2 transactions} \} \)

Example 1: For prices = [3, 3, 5, 0, 0, 3, 1, 4], the maximum profit is 6.

Example 2: For prices = [1, 2, 3, 4, 5], the maximum profit is 4.

Example 3: For prices = [7, 6, 4, 3, 1], no profit is possible so the answer is 0.

inputFormat

The input is given from standard input (stdin) in the following format:

• The first line contains an integer n representing the number of days.
• The second line contains n space-separated integers where each integer represents the stock price on that day.

If n is 0, there will be no prices provided and you should output 0.

outputFormat

Output a single integer representing the maximum profit that can be achieved with at most two transactions. The output should be written to standard output (stdout).

## sample

8
3 3 5 0 0 3 1 4

6

</p>