Dọc một tuyến phố có ~n~ toà nhà xếp thành một hàng từ trái sang phải, được đánh số từ ~1~ đến ~n~; toà nhà thứ ~i~ cao ~h_i~ mét. Câu lạc bộ Nhiếp ảnh muốn khảo sát tầm nhìn từ sân thượng của từng toà nhà để chọn điểm chụp ảnh toàn cảnh.

Đứng trên nóc toà nhà ~i~ và nhìn về bên trái, người quan sát lần lượt nhìn thấy các toà ~i-1, i-2, \ldots~ cho đến khi gặp toà nhà đầu tiên có chiều cao lớn hơn hoặc bằng ~h_i~: toà nhà này vẫn được nhìn thấy, nhưng nó che khuất mọi toà nhà nằm bên trái nó. Nếu không có toà nhà nào như vậy thì người quan sát nhìn thấy tất cả các toà nhà bên trái.

Gọi ~c_i~ là số toà nhà nhìn thấy được từ nóc toà nhà ~i~. Nói cách khác, gọi ~j~ là chỉ số lớn nhất thoả mãn ~j < i~ và ~h_j \ge h_i~: nếu tồn tại ~j~ thì ~c_i = i - j~, ngược lại ~c_i = i - 1~ (đặc biệt ~c_1 = 0~).

Yêu cầu

Hãy tính tổng ~c_1 + c_2 + \cdots + c_n~.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên ~n~;
• Dòng thứ hai chứa ~n~ số nguyên ~h_1, h_2, \ldots, h_n~.

Kết quả ra

Ghi ra một số nguyên duy nhất là tổng tìm được.

Ràng buộc

~1 \le n \le 5 \cdot 10^5~; ~1 \le h_i \le 10^9~.

• Subtask 1 (30% số điểm – test 01–06): ~n \le 5000~;
• Subtask 2 (10% số điểm – test 07–08): dãy chiều cao giảm ngặt, tức là ~h_1 > h_2 > \cdots > h_n~;
• Subtask 3 (20% số điểm – test 09–12): ~h_i \le 100~;
• Subtask 4 (40% số điểm – test 13–20): không có ràng buộc bổ sung.

Lưu ý: kết quả có thể vượt quá phạm vi kiểu số nguyên 32 bit.

Ví dụ

Dữ liệu vào mẫu 1

5
3 1 2 5 2

Kết quả ra mẫu 1

7

Giải thích

• Toà ~1~ không có toà nào bên trái: ~c_1 = 0~;
• Toà ~2~ (cao ~1~) nhìn thấy toà ~1~ (cao ~3 \ge 1~) và bị chặn ngay: ~c_2 = 1~;
• Toà ~3~ (cao ~2~) nhìn thấy toà ~2~, rồi toà ~1~ (cao ~3 \ge 2~) thì bị chặn: ~c_3 = 2~;
• Toà ~4~ (cao ~5~) cao hơn mọi toà bên trái nên nhìn thấy cả ba: ~c_4 = 3~;
• Toà ~5~ (cao ~2~) nhìn thấy toà ~4~ (cao ~5 \ge 2~) và bị chặn ngay: ~c_5 = 1~.

Tổng cần tìm là ~0 + 1 + 2 + 3 + 1 = 7~.