Maximizing Stock Profit with Two Transactions

You are given an array of integers, prices, where prices[i] represents the stock price on day i. Your task is to determine the maximum profit that can be achieved by completing at most two transactions. A transaction is defined as buying one share of the stock and then selling that share later. Note that you cannot engage in multiple transactions concurrently, meaning you must sell the stock before you buy it again.

The problem can be solved using dynamic programming. One can define a state dp[i][j] which represents the maximum profit attainable using at most i transactions up to day j. The transition is formulated as follows:

$$\text{dp}[i][j] = \max\Big(\text{dp}[i][j-1],\; prices[j] + \max_{0 \leq k < j} (\text{dp}[i-1][k] - prices[k])\Big) $$

Implement an algorithm that reads the input from standard input (stdin) and outputs the result to standard output (stdout).

inputFormat

The input is given in two lines. The first line contains a single integer n, the number of days. The second line contains n space-separated integers representing the stock prices for each day.

If n is zero, then there are no prices available.

outputFormat

Output a single integer representing the maximum profit achievable with at most two transactions. The answer should be printed to standard output (stdout).

## sample

8
3 3 5 0 0 3 1 4

6