Cho một dãy số nguyên không âm h gồm n phần tử. Phần tử hᵢ biểu diễn chiều cao của một cột tường tại vị trí i. Mỗi cột có độ rộng bằng 1.

Sau khi trời mưa, nước có thể được giữ lại giữa các cột tường. Hãy tính tổng lượng nước có thể được giữ lại sau cơn mưa.

Input

• Dòng đầu tiên chứa số nguyên n — số lượng cột ( 1 ≤ n ≤ 2 × 10⁵ ).
• Dòng thứ hai chứa n số nguyên h₁, h₂, ..., hₙ ( 0 ≤ hᵢ ≤ 10⁹ ) .

Output

In ra một số nguyên duy nhất — tổng lượng nước có thể giữ lại sau cơn mưa.

Subtask

• Subtask 1 — 20% : 1 ≤ n ≤ 500 , 0 ≤ hᵢ ≤ 10⁴
• Subtask 2 — 20% : 1 ≤ n ≤ 5 × 10³ , 0 ≤ hᵢ ≤ 10⁵
• Subtask 3 — 30% : 1 ≤ n ≤ 2 × 10⁵ , 0 ≤ hᵢ ≤ 10⁵
• Subtask 4 — 30% : Không có ràng buộc gì thêm.

Ví dụ

Sample Input

11
0 1 0 2 1 0 3 1 0 1 2

Sample Output

8

Giải thích