Trong một thế giới nơi mọi thứ được sắp xếp theo thứ tự, nhà nghiên cứu trẻ Aurelia đang phân tích một chuỗi dữ liệu cổ đại. Mỗi số trong dãy biểu thị một mức năng lượng. Cô tin rằng trong dãy tồn tại những bộ ba hoàn hảo, nơi năng lượng tăng dần một cách ổn định qua thời gian. Một bộ ba chỉ số ~i, j, k~ được gọi là hợp lệ nếu: $$ ~a_i < a_j < a_k~$$ $$ ~i < j < k~$$

Những bộ ba như vậy được xem là dấu hiệu của sự cân bằng hoàn hảo.

Yêu cầu: Hãy giúp Aurelia đếm xem có bao nhiêu bộ ba như vậy trong dãy.

Input

• Dòng đầu tiên gồm số nguyên dương ~n (n \leq 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_i (1 \le i \le n ; |a_i| \le 10^9)~ cách nhau bởi dấu cách.

Output

• Gồm một số nguyên duy nhất là yêu cầu bài toán.

Ví dụ

Example input 1

5
1 2 3 4 5

Example output 1

10

Example input 2

6
1 3 2 4 5 2

Example output 2

7

Ràng buộc