Lượng nước


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 98M

Author:
Problem types

Nhà mình làm lại cái nhà

Mua những cái cọc đóng tra làm nền

Mấy ngày mưa ướt liên miên

Hỏi bao nhiêu nước đang trên nền nhà

Cho \(n\) cái cọc bê tông được đóng thành một hàng dài sát nhau, khi mưa rơi xuống thì nước mưa trên các cọc thấp sẽ còn đọng lại nếu có những cọc cao ngăn cho, giả sử bề ngang của mỗi cái cọc là một đơn vị hãy tính lượng nước đọng lại trên các cọc này

Input

Dòng đầu chứa số nguyên dương \(n\) có giá trị không vượt quá \(10^6\)

Dòng sau là \(n\) số tự nhiên đại diện cho chiều cao của \(n\) cái cọc đứng lần lượt sát nhau đảm bảo đọng nước ở đó không thoát được có giá trị không vượt quá \(32768\)

Output

Một số tự nhiên là tổng só nước đọng lại trên tất cả các cọc biết rằng trời mưa mấy ngày qua đảm bảo lượng nước vô hạn đã rót xuống

Ví dụ

Input

7
3 7 2 1 5 2 4

Output

9

Giải thích Lượng nước đọng lại ở cột 3 cột 4 thành một vùng và cột 6 như hình vẽ
Lượng nước

tichpx

Comments

There are no comments at the moment.