Chú chim cánh cụt Pengu sống ở Bắc Cực cùng các bạn bè mình, mặc dù không bay được như các loài chim khác, nhưng các chú chim cánh cụt lại rất thích được bay lượn trên bầu trời. Pengu đã quyết định thực hiện ước mơ đó cùng các bạn của mình. Thật may mắn là nơi Pengu sinh sống lại có ~N~ đỉnh núi băng được đánh số từ 1 đến ~N~, đỉnh núi thứ ~i~ có độ cao ~H_i~.

Pengu quyết định chọn 3 đỉnh núi ~x, y, z~. Chú chim dự định sẽ đặt cầu trượt tại ~y~ và có thể trượt về phía đỉnh ~x, z~. Để tránh va chạm khi các bạn sử dụng cầu trượt, Pengu đã quyết định chọn ~x, z~ ở hai phía của ~y~ và độ cao cũng thấp hơn độ cao tại ~y~.

Pengu đã suy tính rất kĩ và đã lên các phương án để tìm các đỉnh ~(x, y, z)~ sao cho ~1 \le x < y < z \le N~ và ~H_x < H_y, H_z < H_y~.

Yêu cầu: Hỏi có bao nhiêu cách chọn ~(x, y, z)~ thỏa mãn yêu cầu?

Input

• Dòng đầu tiên ghi số ~N~ (~3 \le N \le 3 \times 10^5~).
• Dòng tiếp theo ghi ~N~ số ~H_1, H_2, \dots, H_N~ (~0 \le H_i \le 10^{18}~) là độ cao các đỉnh núi băng.

Output

• Số lượng cách chọn ~(x, y, z)~ thỏa mãn ~1 \le x < y < z \le N~ và ~H_x < H_y, H_z < H_y~.

Sample Input 1

5
0 1 1 0 1

Sample Output 1

2

Sample Input 2

6
500 20 900 0 900 70

Sample Output 2

7