Maximum Profit with Two Transactions

You are given the stock prices for a single day, where each price represents the value of a stock at a particular time. You are allowed to complete at most two transactions (i.e. two buy‐sell pairs), but you must sell the stock before you buy again. Note that you cannot engage in multiple transactions at the same time.

The goal is to maximize the total profit you can achieve by executing at most two transactions.

Formally, let (P = [p_0, p_1, \ldots, p_{n-1}]) be the array of stock prices. A transaction consists of buying on day (i) and selling on day (j) with (0 \leq i < j < n). You are allowed to perform at most two non-overlapping transactions.

Your task is to compute the maximum profit possible.

inputFormat

The input is given via standard input. The first line contains an integer (n) representing the number of stock prices. The second line contains (n) space-separated integers (p_0, p_1, \ldots, p_{n-1}), where each integer represents the stock price at that time.

outputFormat

Output the maximum profit that can be obtained using at most two transactions. The result should be printed to standard output.## sample

8
3 3 5 0 0 3 1 4

6