Optimal Single-Trade Profit

Time Limit: 2sMemory: 256MB

Problem

You are a junior trader given historical tick data for an asset over n time intervals. Your desk head wants you to determine the maximum profit achievable from a single round-trip trade: buy at one time and sell at a strictly later time.

If no profitable trade is possible (prices never increase), report a profit of 0.

Input Format

First line: integer n (number of time intervals).
Second line: n space-separated integers representing prices at each interval.

Output Format

A single integer representing the maximum achievable profit from one buy and one sell.

Examples

Example 1

Input(First line: integer n (number of time intervals).)

6
310 215 480 390 570 120

Output

Buy at 215 (day 1), sell at 570 (day 4). Profit = 570 - 215 = 355.

Example 2

Input(First line: integer n (number of time intervals).)

4
500 400 300 200

Output

Prices only decrease, so no profitable trade exists.

Constraints

•1 ≤ n ≤ 10^5
•0 ≤ prices[i] ≤ 10^4

Loading interactive editor…