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 điề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?

Dữ liệu đầu vào

Gồm hai dòng:

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

Dữ liệu đầu ra

Gồm một số nguyên duy nhất 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.

Ràng buộc dữ liệu

• 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~.

Ví dụ

Ví dụ 1

INPUT

5
7 8 5 9 4

OUTPUT

6

Giải thích: Có ~6~ cặp học sinh trong hàng mà học sinh đứng trước cao hơn học sinh đứng sau là ~(7, 5); (7, 4); (8, 5); (8, 4); (5, 4); (9, 4)~.