Bẫy nước

Bối cảnh

Cho một mảng \(N\) số nguyên không âm \(a\) đại diện cho các cột có độ cao \(a_i\) trong đó chiều rộng của mỗi thanh là \(1\), tính toán lượng nước nó có thể giữ lại sau khi mưa. Ví dụ: \(N=5\) và mảng \(a=[3, 0, 2, 0, 4]\) chúng ta sẽ đựng được lượng nước mưa là \(7\) như hình minh họa. Chúng ta có thể đựng \(3\) đơn vị nước từ \(3\) đến \(2\), \(1\) đơn vị trên đầu thanh \(2\) và \(3\) đơn vị từ \(2\) đến \(4\).

Yêu cầu

Input

Dòng đầu tiên nhập vào số nguyên \(N\) \((1 \leq N \leq 10^6)\).

Dòng thứ hai nhập vào các phần tử của mảng \(a\) đại diện cho chiều cao. \((1 \leq a_i \leq 10^6)\).

Output

In ra một số duy nhất là số lượng nước của chúng ta có thể đựng.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

5
3 0 2 0 4

Output

7

Ví dụ 2

Input

12
0 1 0 2 1 0 1 3 2 1 2 1

Output

6

Giải thích ví dụ

1. Ví dụ đầu vào: 3 0 2 0 4

   • Lượng nước giữ lại: 7 là tổng lượng nước có thể đọng lại giữa các cột cao, với nước được giữ lại giữa cột 3 và 2, cũng như giữa cột 2 và 4.

2. Ví dụ đầu ra: 0 1 0 2 1 0 1 3 2 1 2 1

   • Lượng nước giữ lại: 6 từ các khoảng giữa các cột, tính toán dựa trên chiều cao tối đa ở hai bên.

Thông tin học tập

• Buổi: B10
• Concepts: 1D arrays, prefix/suffix maxima
• Giới hạn kiến thức: B01-B10
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 25