Public submissions
Source code of every submission to this problem in this contest will be visible for everyone since 2016-01-01 00:00:00.
Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

LHPGIFT - Phát thưởng

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

Added by:Duc M. Pham
Date:2016-02-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Lọ :>
Public source code since: 2016-01-01 00:00:00
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.