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.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• 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~).

Dữ liệu đầu ra

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

Ràng buộc dữ liệu

• Subtask 1: Có ít nhất 33% số test có ~N \le 100~;
• Subtask 2: Có ít nhất 50% số test có ~N \le 1000~;
• Subtask 3: Số test còn lại không có ràng buộc gì thêm.

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)~.

~\rightarrow~ Số cặp robot có thể nhận diện được nhau là ~6~.