EIU Programming Practices and Exams

Ngày cuối HK1 đã đến. Giáo viên của thằng đần CannotSummonGa gọi cả lớp ra xếp hàng và lì xì cả lớp trước khi nghỉ Tết. Thành tích của học sinh được biểu diễn bằng một con số và người giáo viên đó muốn lì xì theo quy luật: với 2 người đứng cạnh nhau, người có thành tích ít hơn phải nhận được tiền ít hơn người có thành tích cao hơn và mỗi bạn phải được đảm bảo có tiền lì xì (ít nhất là 1$). Hãy tính số tiền ít nhất để người giáo viên đó lì xì hết cả lớp.

Input

Dòng đầu là số nguyên dương N <= 5.000.000 là số học sinh.

Dòng tiếp theo là N số nguyên biểu diễn thành tích của N học sinh. (0<a[i]<1001).

Output

Số tiền ít nhất mà giáo viên cần để lì xì cả lớp.

Example

Input:
3
1 2 2

Output:
4