Sắp xếp

Sắp xếp nổi bọt (Bubble Sort) là một trong những thuật toán đơn giản và dễ hiểu. Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy phần tử bằng cách liên tục lập lại việc so sánh hai phần tử liền kề và hoán đổi vị trí của chúng nếu chung không theo thứ tự mong muốn. Quá trình này được lặp lại cho đến khi toàn bộ dãy đã được sắp xếp hoàn chỉnh.

Yêu cầu: Cho một dãy gồm $n$ phần tử hãy viết chương trình đêm số lần hoán đổi vị trí các phần tử theo thuật toán sắp xếp nổi bọt để sắp xếp dãy tăng dần.

Đọc từ file SAPXEP.INP gồm:

• Dòng thứ nhất chứa số nguyên dương $(1 \le a_i \le 2.10^5)$
• Dòng thứ hai chứa số nguyên dương cách nhau bằng khoảng trắng $a_1, \dots, a_i, \dots, a_n$ $(1 \le a_i \le 10^9)$

Ghi ra file SAPXEP.OUT một số nguyên duy nhất cho biết số lần hoán đổi vị trí các phần tử theo thuật toán sắp xếp trên.

• 80% số điểm bài thi: $1 \le n \le 10^3$
• 100% số điểm bài thi: $1 \le n \le 2.10^5$