Xếp hàng

Tham gia buổi diễu hành kỉ niệm ngày lễ Quốc khánh có $n$ học sinh được xếp thành một hàng dài. Các học sinh được đánh số từ 1 đến $n$ từ đầu hàng đến cuối hàng, học sinh thứ $i$ có chiều cao $a_i$. Thầy giáo phụ trách nhận thấy có một số học sinh đứng phía trước có chiều cao cao hơn những học sinh đứng sau, điều này làm giảm tính thẩm mỹ khi đoàn diễu hành qua lễ đài. Độ thẩm mỹ của đoàn diễu hành phụ thuộc vào số cặp học sinh trong hàng mà học sinh đứng trước cao hơn học sinh đứng sau, số cặp này càng nhiều thì độ thẩm mỹ càng giảm.

Yêu cầu: Hãy cho biết có bao nhiêu cặp học sinh trong hàng mà học sinh đứng trước cao hơn học sinh đứng sau?

Cho từ tệp văn bản XEPHANG.INP có dạng:

• Dòng thứ nhất ghi số nguyên dương $n$ ($1 < n \le 10^6$);
• Dòng thứ hai ghi $n$ số nguyên dương $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6, i = 1..n$).

Ghi ra tệp văn bản XEPHANG.OUT gồm một dòng ghi một số nguyên là số cặp học sinh trong hàng mà học sinh đứng trước cao hơn học sinh đứng sau.

• Có 70% số điểm tương ứng 70% số test có $1 \le n \le 10^3$.
• Có 20% số điểm tương ứng 20% số test có $10^3 < n \le 10^5$.
• Có 10% số điểm tương ứng 10% số test có $10^5 < n \le 10^6$.