Trong thị trường chứng khoán, giá cổ phiếu luôn biến động từng ngày. Một nhà đầu tư thông minh không chỉ nhìn vào giá hiện tại, mà cần biết chọn thời điểm mua thấp - bán cao để tối ưu lợi nhuận.

Giả sử bạn được cung cấp một mảng prices, trong đó:

• prices[i] là giá cổ phiếu tại ngày thứ ~i~.

• Bạn chỉ được thực hiện một lần mua và một lần bán.

• Ngày bán luôn phải sau ngày mua .

• Lợi nhuận được tính bằng: profit = giá bán - giá mua.

Hãy xác định lợi nhuận tối đa mà bạn có thể đạt được nếu chọn đúng thời điểm giao dịch.

Input

Một mảng số nguyên prices mô tả giá cổ phiếu theo từng ngày.

Output

Một số nguyên biểu thị lợi nhuận lớn nhất có thể thu được.

Ví dụ

Input:

7 1 5 3 6 4

Output:

5

Giải thích:

Mua ở ngày 2 (giá = 1)

Bán ở ngày 5 (giá = 6)

Lợi nhuận tối đa = 6 - 1 = 5

Đây chính là chiến lược "mua thấp - bán cao" cơ bản mà mọi nhà đầu tư đều theo đuổi.