Phòng thí nghiệm Vật liệu vừa nhận về ~n~ mẫu thử, đặt thành một hàng trên giá theo đúng thứ tự giao hàng: mẫu đứng thứ ~i~ (tính từ trái sang) có khối lượng ~a_i~ microgam. Theo quy trình, các mẫu trên giá cần được xếp theo khối lượng không giảm từ trái sang phải.

Trước khi sắp xếp lại, kỹ thuật viên muốn đánh giá xem hàng mẫu hiện tại lộn xộn tới mức nào. Một cặp vị trí ~(i, j)~ với ~i < j~ được gọi là cặp sai thứ tự nếu mẫu đứng trước nặng hơn hẳn mẫu đứng sau, tức là ~a_i > a_j~. Hai mẫu có khối lượng bằng nhau không tạo thành cặp sai thứ tự. Độ lộn xộn của hàng mẫu là số cặp sai thứ tự.

Yêu cầu

Cho dãy ~a_1, a_2, \ldots, a_n~, hãy tính độ lộn xộn của dãy, tức là số cặp chỉ số ~(i, j)~ thoả mãn ~1 \le i < j \le n~ và ~a_i > a_j~.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên ~n~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~, các số cách nhau bởi dấu cách.

Kết quả ra

Ghi ra một số nguyên duy nhất là độ lộn xộn của dãy.

Ràng buộc

~1 \le n \le 2 \cdot 10^5~; ~1 \le a_i \le 10^9~.

• Subtask 1 (30% số điểm – test 01–06): ~n \le 5000~;
• Subtask 2 (20% số điểm – test 07–10): ~a_i \le 100~;
• Subtask 3 (20% số điểm – test 11–14): dãy là một hoán vị của ~1, 2, \ldots, n~;
• Subtask 4 (30% số điểm – test 15–20): không có ràng buộc bổ sung.

Lưu ý: kết quả có thể vượt quá phạm vi kiểu số nguyên 32 bit.

Ví dụ

Dữ liệu vào mẫu 1

6
3 1 4 1 5 2

Kết quả ra mẫu 1

6

Giải thích

Sáu cặp sai thứ tự là ~(1, 2)~, ~(1, 4)~, ~(1, 6)~ (mẫu nặng ~3~ đứng trước các mẫu nặng ~1~, ~1~, ~2~); ~(3, 4)~, ~(3, 6)~ (mẫu nặng ~4~ đứng trước các mẫu nặng ~1~, ~2~) và ~(5, 6)~ (mẫu nặng ~5~ đứng trước mẫu nặng ~2~). Cặp ~(2, 4)~ gồm hai mẫu cùng nặng ~1~ nên không được tính.