Cho giá cổ phiếu của một công ty trong ~n~ ngày, được biểu diễn bởi ~a_1, a_2, \ldots, a_n~, trong đó ~a_i~ là giá cổ phiếu vào ngày thứ ~i~.

Bạn chỉ được phép thực hiện đúng một giao dịch, bao gồm:

• Mua vào một ngày nào đó ~i~.
• Bán ra vào một ngày sau đó ~j~ (~j > i~).

Hãy tìm lợi nhuận tối đa có thể đạt được từ giao dịch này. Nếu không thể thu được lợi nhuận (tức là giá luôn giảm), kết quả là ~0~.

Scoring

• Subtask ~1~ ~(50\%)~: ~n \leq 2000~, ~1 \leq a_i \leq 10^9~;
• Subtask ~2~ ~(50\%)~: ~n \leq 10^5~, ~1 \leq a_i \leq 10^9~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - số ngày (~1 \leq n \leq 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10^9~) - giá cổ phiếu từng ngày.

Output

Một số nguyên duy nhất - lợi nhuận tối đa có thể đạt được.

Example input 1

6
7 1 5 3 6 4

Example output 1

5

Note 1

• Mua vào ngày 2 (có giá là 1) và bán vào ngày 5 (có giá là 6).
• Lợi nhuận: ~6 - 1 = 5~.