...Trong chiến dịch Điện Biên Phủ, ngày 30 tháng 3 năm 1954 quân ta đồng loạt tấn công các cứ điểm phía Đông phân khu trung tâm như đồi E1, D1, C1, C2, A1,… Ta chiếm phần lớn các cứ điểm của địch, tạo điều kiện để bao vây, chia cắt và khống chế địch. Sau đợt này, Mỹ khẩn cấp viện trợ cho Pháp tăng cường lực lượng để tái chiếm. Trước tình hình khẩn cấp, ban chỉ huy chiến dịch đã lên kế hoạch phòng thủ bằng cách đưa pháo lên các cứ điểm cao...

Sau giờ học, Tý say sưa trong bài giảng môn Lịch sử nên nghĩ ra bài toán nhờ các bạn tìm lời giải như sau:

Cho ~n~ cứ điểm được đánh số từ ~1~ đến ~n~, cứ điểm thứ ~i~ có độ cao ~h_i~. Tý muốn chọn ~3~ cứ điểm ~x, y, z~ và đặt pháo tại đỉnh cứ điểm ~y~ sao cho ~1 \le x < y < z \le n~ và ~h_x < h_y > h_z~. Tý muốn đặt pháo tại cứ điểm ~y~ cao hơn hai bên để có thể phòng thủ được hai cứ điểm ~x~ và ~z~ thấp hơn.

Yêu cầu: Hãy đếm có bao nhiêu cách chọn bộ cứ điểm ~(x, y, z)~ thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên ghi số ~n~ ~(3 \le n \le 3 \cdot 10^5)~ là số cứ điểm.

• Dòng tiếp theo chứa ~n~ số nguyên không âm ~h_1, h_2, \dots, h_n~ ~(0 \le h_i \le 10^{18})~ lần lượt là độ cao của cứ điểm thứ ~i~.

Output

Ghi ra một số nguyên duy nhất là số lượng cách chọn bộ cứ điểm ~(x, y, z)~ thỏa mãn.

Scoring

Sample Input 1

5
10 18 18 10 18

Sample Output 1

2

Sample Input 2

6
15 2 60 0 60 7

Sample Output 2

7

Notes

• Trong ví dụ thứ nhất, các bộ cứ điểm: ~(1, 2, 4)~ và ~(1, 3, 4)~.

• Trong ví dụ thứ hai, các bộ cứ điểm: ~(1, 3, 4)~, ~(1, 3, 6)~, ~(1, 5, 6)~, ~(2, 3, 4)~, ~(2, 3, 6)~, ~(2, 5, 6)~ và ~(4, 5, 6)~.