Vườn trên mái (Rooftop Garden)

Nguồn: Baekjoon Online Judge

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ tòa nhà xếp từ trái sang phải. Chủ của tòa nhà $i$ có thể nhìn thấy mái của các tòa nhà liên tiếp bên phải cho đến trước tòa nhà đầu tiên có chiều cao lớn hơn hoặc bằng tòa nhà $i$. Hãy tính tổng số mái nhà được nhìn thấy bởi tất cả chủ tòa nhà.

Input

Dòng đầu chứa $N$. Mỗi trong $N$ dòng tiếp theo chứa chiều cao của một tòa nhà, theo thứ tự từ trái sang phải.

Output

In một số nguyên: tổng số cặp quan sát theo mô tả.

Subtask

• Subtask 1 (30 điểm): $N\le2000$; các điều kiện khác giữ nguyên.
• Subtask 2 (70 điểm): $1\le N\le80000$, $1\le H_i\le10^9$.

Ví dụ

Input

6
10
3
7
4
12
2

Output

5

Giải thích

Xét từng tòa nhà từ trái sang phải:

• Tòa cao $10$ nhìn thấy ba mái cao $3,7,4$. Tòa cao $12$ là tòa đầu tiên có chiều cao ít nhất $10$, nên tầm nhìn dừng trước tòa này: đóng góp $3$.
• Tòa cao $3$ gặp ngay tòa cao $7\ge3$, nên không nhìn thấy mái nào: đóng góp $0$.
• Tòa cao $7$ nhìn thấy mái cao $4$, rồi bị tòa cao $12\ge7$ chặn: đóng góp $1$.
• Tòa cao $4$ bị tòa cao $12\ge4$ chặn ngay: đóng góp $0$.
• Tòa cao $12$ nhìn thấy mái cao $2$: đóng góp $1$.
• Tòa cuối cùng không có tòa nào bên phải: đóng góp $0$.

Tổng số mái nhìn thấy là $3+0+1+0+1+0=5$, nên output là 5.