Nhật ký số phép so sánh khi Merge Sort

Bối cảnh và bài toán

Một công cụ giảng dạy chạy Merge Sort chuẩn: chia đoạn tại mid=(l+r)/2; sort nửa trái trước, nửa phải sau; khi merge, mỗi lần so sánh trực tiếp hai phần tử đầu của hai nửa chưa cạn được tính là một phép so sánh. Các bước copy phần còn lại không tính.

Yêu cầu

In tổng số phép so sánh của quy trình Merge Sort chuẩn và mảng sau khi sắp xếp.

Input

• Dòng 1: n.
• Dòng 2: n số nguyên.

Output

Dòng 1 in số phép so sánh. Dòng 2 in mảng tăng dần.

Ràng buộc

• 1 <= n <= 2 * 10^5
• |a[i]| <= 10^9

Chấm điểm

Ví dụ 1

Input

2
2 1

Output

1
1 2

Giải thích. Hai nửa một phần tử được so sánh đúng một lần.

Ví dụ 2

Input

1
7

Output

0
7

Giải thích. Đoạn một phần tử là base case, không cần merge.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.