Nhận diện

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 (đượ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 đó (nghĩa là mọi robot đứng giữa đều có chiều cao không vượt quá chiều cao của robot thấp hơn trong hai robot \(A\), \(B\)).

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

Input

Dữ liệu vào 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\)).

Ràng buộc:

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

Output

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

Example

Input:

5
2
4
1
2
2

Output:

6

Note

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