Maximum Profit from Two Stock Transactions

You are given an array of stock prices, where the i-th element represents the price of a given stock on day i. You are allowed to complete at most two transactions (a buy followed by a sell) in order to maximize your profit. Note that you must sell the stock before you can buy again. The goal is to determine the maximum profit that can be achieved.

Hint: You can use dynamic programming to compute the maximum profit up to each day from the left and the maximum profit from each day to the right, then combine these values.

Formally, if we let \(P[i]\) denote the stock price on day \(i\), you need to choose two pairs \((i, j)\) and \((k, l)\) with \(i \le j < k \le l\) such that the profit \((P[j]-P[i]) + (P[l]-P[k])\) is maximized. If no profitable transactions exist, the answer should be 0.

inputFormat

The input is given in two lines. The first line contains an integer n representing the number of days. The second line contains n space-separated integers representing the stock prices.

outputFormat

Output a single integer which is the maximum profit that can be achieved with at most two transactions.

## sample

8
3 3 5 0 0 3 1 4

6

</p>