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.

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

Yêu cầu

Cho dãy số nguyên ~a[1],a[2],a[3],...,a[n]~.

Đếm bộ ba số ~i, j, k~ hợp lệ.

Input:

• Dòng đầu tiên gồm số nguyên dương ~n (n≤10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a[i] (1≤i≤n ; |a[i]|≤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ụ:

Input 1:

5
1 2 3 4 5

Output 1:

10

Input 2:

6
1 3 2 4 5 2

Output 2:

5

Ràng buộc