Cho \(n\) cột có chiều cao \(h_1, h_2, \dots, h_n\) được đặt cạnh nhau trên một đường thẳng. Sau trận mưa, nước sẽ đọng lại giữa các cột tạo thành các vũng nước.

Tính tổng lượng nước đọng lại (tổng số ô nước giữa các cột).

Sử dụng hai con trỏ: duy trì chiều cao cột chắn lớn nhất bên trái và bên phải, xử lý cột thấp hơn trước.

Input

Dòng đầu chứa \(n\) (\(3 \le n \le 10^5\)).
Dòng hai chứa \(n\) số \(h_i\) (\(1 \le h_i \le 10^9\)).

Output

In ra tổng lượng nước đọng.

Example

6
3 0 0 2 0 4

Output:

10