Best Time to Buy and Sell Stock 2

You are given an array of prices, where $price{s}_i$ contains the price of a stock on the $i$-th day.

Each day, you can decide whether to buy and/or sell stocks. At any given time, you can own at most one stock.

Find the maximum profit that can be obtained.

Input

The first line contains the size $n(n\le 10^5)$ of the price array. The second line contains the price array - $n$ integers, each not exceeding $10^4$.

Output

Print the maximum profit that can be obtained. If it is impossible to obtain a profit, output $0$.

Examples