Caisa và các cột trụ

Có $n+1$ cột trụ được đánh số từ $0$ đến $n$. Trụ số $0$ có độ cao bằng $0$, trụ số $i$ (với $i>0$) có độ cao $h_i$.

Người chơi bắt đầu đứng ở trụ số $0$ với năng lượng bằng $0$. Mỗi bước, người chơi có thể nhảy từ trụ hiện tại (số $k$) sang trụ kế tiếp (số $k+1$). Sau khi nhảy, năng lượng của người chơi thay đổi thêm $h_k-h_{k+1}$ (nếu giá trị này âm, người chơi mất năng lượng).

Tại mọi thời điểm, năng lượng của người chơi phải luôn không âm. Mục tiêu là đến được trụ số $n$.

Người chơi có thể trả $1$ đô la để tăng độ cao của một trụ bất kỳ (kể cả trụ số $0$) thêm $1$ đơn vị, và có thể làm điều này nhiều lần tùy ý. Hãy tính số đô la nhỏ nhất cần trả để hoàn thành trò chơi.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $h_1,h_2,\dots ,h_n$.

Dữ liệu ra

In ra một số nguyên — số đô la nhỏ nhất phải trả.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le h_i\le {10}^5$

Ví dụ