Bubble sort là một thuật toán sắp xếp bao gồm nhiều vòng lặp. Ở mỗi vòng lặp, thuật toán sẽ duyệt mảng từ trái sang phải và hoán đổi (swap) bất kỳ hai phần tử liền kề nào nằm sai thứ tự.

Cho một mảng gồm n số nguyên, hãy tính số vòng lặp mà thuật toán bubble sort cần để sắp xếp mảng theo thứ tự tăng dần.

Dữ liệu vào:

Dòng đầu tiên: số nguyên n — kích thước mảng.

Dòng thứ hai: n số nguyên x₁, x₂, …, xₙ — các phần tử trong mảng.

Dữ liệu ra:

In ra một số nguyên: số vòng lặp cần thiết để bubble sort sắp xếp xong mảng

Ràng buộc:

~1 \le n \le 2 \cdot 10^5~

~1 \le x_i \le 10^9~

Ví dụ :

Input:

5
3 2 4 1 4

Output:

3