Một cơn mưa siêu to khổng lồ vào ngày hôm qua là dấu hiệu cho sự mở đầu của mùa mưa hằng năm. Sau cơn mưa hôm qua, Rùa 🐢 kiểm tra mái nhà của mình thì thấy nước mưa bị ứ đọng lại. Thấy vậy, Rùa tự hỏi lượng nước có thể đọng trên nhà mình nhiều nhất là bao nhiêu?

Rùa liền chạy xuống tầng hầm để tìm bản thiết kế mái nhà của mình. Tuy mái nhà của mình nhìn rất mịn, hầu như không có gồ ghề, nhưng khi phóng thật to lên thì nó giống như những hình cột có cùng chiều rộng và xếp liền nhau. Vì vậy, ta có thể biểu diễn nó như một chuỗi số.

Bản thiết kế mái nhà mô tả mái nhà của Rùa bao gồm \(N\) cột, được cho dưới dạng một chuỗi số \(A\), với \(A_i\) là độ cao của cột thứ \(i\).

Ví dụ với \(N = 7\) và \(A = \{1, 2, 3, 2, 3, 2, 1\}\) thì mái nhà của anh trông như sau:

Với mái nhà trên, sau cơn mưa, sẽ có \(1\) đơn vị mưa đọng lại:

Cho chuỗi số mô tả mái nhà của Rùa, hãy tính có bao nhiêu đơn vị nước mưa đọng lại ngay sau một cơn mưa thật thật dài?

Input

• Dòng đầu tiền chứa một số nguyên dương \(N (1 \leq N \leq 2*10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(A_i\) mô tả độ cao của cột thứ \(i\) \((0 \leq A_i \leq 10^9)\)

Output

In ra một số nguyên, là số đơn vị nước mưa đọng lại sau cơn mưa.

Example

Test 1

Input

7
1 2 1 2 1 2 1

Output

2

Note

Test 2

Input

10
2 1 3 2 4 4 2 3 1 2

Output

4

Note