Trước khi bàn giao các robot tại công ty VBT, có ~N~ robot xếp thẳng hàng để chờ đến lượt kiểm tra hệ thống. Mỗi robot có chiều cao khác nhau (được tính bằng đơn vị đo riêng biệt).

Trong lúc chờ đợi, các robot có thể quét và nhận diện những robot quen biết xung quanh để trao đổi với nhau. Tuy nhiên, do cảm biến bị hạn chế, không phải robot nào cũng nhận diện được nhau.

Hai robot A và B đứng trong hàng có thể nhận diện được nhau nếu thỏa mãn một trong hai điều kiện sau:

• Robot A và robot B đứng ngay cạnh nhau trong hàng.
• Giữa robot A và robot B không có robot nào cao hơn hẳn một trong hai robot đó.

Yêu cầu: Đếm số cặp robot có thể nhận diện được nhau trong hàng.

Input

Đọc từ file văn bản B3ND.INP gồm:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(2 \le N \le 10^5)~ là số lượng robot.
• ~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 robot (tính theo đơn vị đo riêng biệt, giá trị không lớn hơn ~2 \times 10^9~).

Output

Ghi ra tệp văn bản B3ND.OUT một số nguyên duy nhất là số cặp robot có thể nhận diện được nhau.

Ví dụ

Ví dụ 1

Input

5
2
4
1
2
2

Output

6

Giải thích: Có 4 cặp robot thỏa mãn điều kiện thứ nhất: các cặp robot ở vị trí (1, 2), (2, 3), (3, 4), (4, 5).

Có 2 cặp robot thỏa mãn điều kiện thứ hai: các cặp robot ở vị trí (2, 4), (2, 5).

Số cặp robot có thể nhận diện được nhau: 6.

Giới hạn

• ~2 \le N \le 10^5~; chiều cao của mỗi robot là số nguyên dương không lớn hơn ~2 \times 10^9~.
• Subtask 1: Có ít nhất 33% số test có ~N \le 10^2~;
• Subtask 2: Có ít nhất 50% số test có ~N \le 10^3~;
• Subtask 3: Số test còn lại không có ràng buộc gì thêm.