---
# System prepended metadata

title: Solution Trò chơi trên dãy số

---

# Solution Trò chơi trên dãy số

Với mỗi vị trí $i$ có $1 \leq a_i \leq n$, ta tính $f_i$ là số lần dịch phải cần thiết để đưa $a_i$ về đúng vị trí.
Ta tính $cnt_x$ là số lượng vị trí $i$ có $f_i = x$.
Nhận thấy rằng các thao tác biến đổi không ảnh hướng đến nhau. Giả sử ta thực hiện $x$ lần dịch phải, thì số thao tác cần thiết để biến đổi dãy về dạng $1, 2, ..., n$ là $x + n - cnt_x$.

Ta dùng set để lưu lại các giá trị $x - cnt_x$, tìm ra giá trị nhỏ nhất để số bước biến đổi là min.