Maximum Profit with At Most Two Stock Transactions

You are given an integer ( n ) and a list of stock prices. The task is to calculate the maximum profit achievable with at most two buy-sell transactions. Each transaction must consist of buying one stock and then later selling it. The profit from a single transaction is defined as ( \text{sell price} - \text{buy price} ), and you are allowed to complete at most two non-overlapping transactions.

Formally, if the stock prices are given as an array ( prices ), you need to choose two pairs of indices ( (i, j) ) and ( (k, l) ) with ( i < j ) and ( k < l ) such that the transactions do not overlap, to maximize ( (prices[j]-prices[i]) + (prices[l]-prices[k]) ). If no profitable transactions are possible, the answer is 0.

inputFormat

The first line of input contains a single integer ( n ).

The second line contains a sequence of space-separated integers representing the stock prices.

outputFormat

Output a single integer representing the maximum profit that can be achieved with at most two transactions.## sample

6
3 3 5 0 0 3 1 4

6