Max Profit with At Most Two Transactions

You are given an array of stock prices where the i-th element represents the price of the stock on day i. Your task is to calculate the maximum profit you can achieve by performing at most two non-overlapping transactions. A transaction is defined as buying and then later selling one share of the stock.

In other words, find two disjoint intervals (or possibly one interval) such that the sum of the profits \( P_1 = price_{sell1} - price_{buy1} \) and \( P_2 = price_{sell2} - price_{buy2} \) is maximized. Note that you must sell the stock before you buy it again.

Hint: You can precompute the maximum profit possible up to each day and the maximum profit possible from each day to the end. The final answer is given by:

[ \text{max_profit} = \max_{0 \leq i < n} { left[i] + right[i] } ]

where \( left[i] \) is the maximum profit from day 0 to day \( i \) and \( right[i] \) is the maximum profit from day \( i \) to day \( n-1 \). If no profit can be made, print 0.

inputFormat

The input is given via standard input and has the following format:

1. The first line contains a single integer \( n \) representing the number of days.
2. If \( n > 0 \), the second line contains \( n \) space-separated integers representing the stock prices.

If \( n = 0 \), there will be no second line and the answer should be 0.

outputFormat

Output a single integer which is the maximum profit that can be achieved with at most two transactions. The output should be printed to standard output.

## sample

8
3 3 5 0 0 3 1 4

6