Cho một hoán vị là một hoán vị của , bạn được thực hiện hai loại phép biến đổi sau:
- Chọn hai phần tử bất kì và tráo đối, loại phép biến đổi này chỉ được thực hiện nhiều nhất một lần;
- Chọn hai phần tử kề nhau và tráo đổi, loại phép biến đổi này được thực hiện nhiều lần.
Yêu cầu: Tính số phép biến đổi ít nhất để đưa hoán vị thành hoán vị .
Dữ liệu vào:
- Dòng đầu chứa số nguyên ;
- Dòng thứ hai chứa số nguyên là một hoán vị của .
Dữ liệu ra:
- Ghi ra thiết bị ra chuẩn một số nguyên là số phép biến đổi ít nhất để đưa hoán vị thành hoán vị .
Ví dụ:
Dữ liệu vào:
Dữ liệu ra:
Giới hạn:
- Có số test ứng với số điểm của bài có ;
- Có số test khác ứng với số điểm của bài có ;
- Có số test khác ứng với số điểm của bài có ;
- Có số test khác ứng với số điểm của bài có ;
- Có số test khác ứng với số điểm của bài có ;
- Có số test còn lại ứng với số điểm của bài có .