Đố vui

Bo là một cậu bé rất yêu thích những con số và thường xuyên được mẹ tạo ra các thử thách toán học nho nhỏ vào dịp cuối tuần.

Hôm nay, mẹ đưa ra bài toán sau:

Cho dãy số \(A\) gồm \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\).

Một cặp số \((a_i, a_j)\) được gọi là cặp số thuận thế nếu thỏa mãn các điều kiện sau:

• \(1 \leq i < j \leq N\)
• \(a_i < a_j\) (tức là phần tử đứng trước nhỏ hơn phần tử đứng sau).

Yêu cầu: Hãy đếm xem trong dãy số \(A\) có bao nhiêu cặp số thuận thế.

Bo đang cần sự giúp đỡ của bạn để giải bài toán này. Hãy giúp Bo tìm ra câu trả lời nhé!

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \leq N \leq 500000\)).
• Dòng thứ 2 chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(0 < a_i \leq 10^9\) với \(\forall i = 1..N\)).

Output

Kết quả bài toán

Example

4
2 4 3 5

5

Scoring

• Có \(70\%\) số test ứng với \(70\%\) số điểm thỏa mãn: \(0 < N \leq 10^3\)
• \(30\%\) số test còn lại ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.