806. Profit from Gold

0

Medium

Given an integer N and an array prices of size N, where prices[i] represents the price of Gold on the ith day, the task is to maximize the profit by choosing a single day to buy gold and a different day in the future to sell gold. The minimum profit that can be earned is 0. Return the maximum profit that can be achieved from this transaction.

Input Format

The first line of input contains an integer N, representing the size of the array. The next line contains N space-separated integers, representing the prices of gold on each day.

Output Format

Output a single integer representing the maximum profit that can be achieved.

Example

Input

5
1 7 8 9 5

Output

8

Constraints

1 <= N <= 10^5

0 <= prices[i] <= 10^4

0 <= prices[i] <= 10^4

Loading...

View Submissions

Console