V11WATER - Nước đọng
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Năm 2011, tình trạng ngập lụt trong thành phố trở lên nghiêm trọng hơn. Vì vậy, mọi người quyết định xây dựng hệ thống mái che cho toàn thành phố.
Mái che có bề rộng là N, được chia làm N phần có độ dài như nhau. Độ cao của mỗi phần là h1, h2, ..., hn. Khi trời mưa, một phần nước sẽ đọng lại trên mái và một phần sẽ thoát ra ngoài theo hai bên trái và phải của mái che. Do đó, thành phố sẽ không phải chịu cảnh mưa lụt như trước.
Nhằm mục đích bảo trì mái che, bạn cần viết chương trình tính lượng nước lớn nhất có thể đọng lại trên mái che.
Input
- Dòng đầu ghi số N. (1 <= N <= 100000)
- Dòng sau ghi N số tự nhiên h1, h2, ..., hn. (1 <= hi <= 100000)
Output
- Gồm một số duy nhất thể hiện lượng nước tìm được.
Giới hạn
- 50% số test có N <= 1000.
Example
Input: 5
1 3 1 2 3
Output:
3
- Người up: voj
- Nguồn bài: VNOI Online 2011Tác giả: Khúc Anh Tuấn