Có N người đứng xếp hàng mua vé xem trận đội tuyển bóng đá Việt Nam gặp Nhật Bản trong ASIAN-Cube.

Hàng quá dài nên tất cả đều sốt ruột và mọi người đều ngó xem phía trước có người quen hay không.

Hai người A và B đứng trong hàng được gọi là nhìn thấy nhau nếu:

• Họ đứng liên tiếp nhau; hoặc
• Giữa họ không có người nào cao hơn A hoặc B.

Yêu cầu: Hãy xác định trong hàng có bao nhiêu cặp người nhìn thấy nhau.

INPUT

• Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 500000) là số người đứng trong hàng;
• N dòng tiếp theo, mỗi dòng chứa một số nguyên dương là chiều cao của một người trong hàng. Chiều cao được đo bằng nanomét và không có ai cao hơn 2³¹ nanomét.

Các chiều cao được liệt kê theo thứ tự của những người đứng trong hàng.

OUTPUT

Ghi ra một số nguyên duy nhất là số lượng cặp người nhìn thấy nhau.

Ví dụ

Sample Input

7
2
4
1
2
2
5
1

Sample Output

10