Phân tích dãy nhịp tim từ vòng đeo tay thông minh HeartFit

Vòng đeo tay HeartFit ghi lại n giá trị nhịp tim (bpm, số nguyên) tại n thời điểm đo liên tiếp trong một buổi tập, theo đúng thứ tự thời gian. Huấn luyện viên cần hai thông tin:

• Số cặp nghịch đảo của dãy nhịp tim, tức số cặp thời điểm (i, j) với i < j nhưng nhịp tim đo tại thời điểm i lại lớn hơn nhịp tim đo tại thời điểm j — số cặp này càng lớn thì nhịp tim dao động càng “lộn xộn” trong buổi tập.
• Dãy nhịp tim sau khi được sắp xếp tăng dần bằng thuật toán chèn (Insertion Sort) đã học, để huấn luyện viên vẽ biểu đồ phân bố nhịp tim từ thấp đến cao.

Em hãy tự thiết kế chương trình (có thể áp dụng lại các bước làm mịn dần đã học cho hàm đếm cặp nghịch đảo Nghichdao(A) và hàm sắp xếp chèn InsertionSort(A)) để giải quyết đồng thời cả hai yêu cầu trên. Chú ý: việc đếm cặp nghịch đảo phải thực hiện trên dãy gốc (trước khi sắp xếp).

Định dạng vào: dòng 1 là số nguyên n (số lần đo); dòng 2 gồm n số nguyên là nhịp tim đo được, cách nhau bởi khoảng trắng.

Định dạng ra: in ra 2 dòng — dòng 1 là số cặp nghịch đảo của dãy gốc; dòng 2 là dãy nhịp tim sau khi sắp xếp tăng dần, các số cách nhau bởi một khoảng trắng.