Bộ ba số nguyên

Cho số nguyên dương \(n\) và dãy gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\).

Yêu cầu: Hãy đếm số lượng bộ ba phần tử có chỉ số khác nhau \(i, j, k\) (\(i < j < k\)) sao cho \(a_i < a_j < a_k\).

Input

Dữ liệu vào có dạng:

• Dòng đầu chứa số nguyên dương \(n\) (\(1 \le n \le 10^5\));

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)), giữa các số cách nhau ít nhất một dấu cách.

Ràng buộc:

• Có \(40\%\) số test ứng với \(40\%\) số điểm có giá trị \(n \le 10^2\).

• Có \(40\%\) số test ứng với \(40\%\) số điểm có giá trị \(n \le 10^3\).

• Có \(20\%\) số test ứng với \(20\%\) số điểm có giá trị \(n \le 10^5\).

Output

In ra một dòng chứa một số nguyên duy nhất là số lượng bộ ba số nguyên tìm được.

Example

Input:

6
3 9 4 7 5 8

Output:

7

Note

Các bộ ba thỏa mãn (theo giá trị): \((3,4,7)\), \((3,4,5)\), \((3,4,8)\), \((3,7,8)\), \((3,5,8)\), \((4,7,8)\), \((4,5,8)\).