def f(l):z=zip(l,range(len(l)));print map(sorted(z).index,z)
Try it online!
A fast algorithm with a simple idea. If we instead need to permute the input list to make it as close to \$(1,2,...,n)\$ as possible, we should just sort it, as proven below. Since we're instead permuting \$(1,2,...,n)\$, we choose the permutation that's ordered the same way as the input list, like in my challenge Imitate an ordering (except the input may have repeats). (Edit: miles pointed out this more identical challenge, where Dennis has this same answer.)
Claim: A permutation of the list \$l\$ that minimizes its distance to \$(1,2,...,n)\$ is \$l\$ sorted.
Proof: Consider some other permutation \$l'\$ of \$l\$. We'll prove it can't be better than \$l\$ sorted.
Pick two indices \$i,j\$ that \$l'\$ has out-of-order, that is where \$i<j\$ but \$l'_i > l'_j\$. We show that swapping them can't increase the distance to \$(1,2,...,n)\$. We note that swap changes the contribution these two elements as follows:
$$ |l'_i - i | + |l'_j - j | \to |l'_i - j | + |l'_j - i|.$$
Here's a neat way to show this can't be an increase. Consider two people walking on a number line, one going from \$l'_i\$ to \$i\$ and the other from \$l'_j\$ to \$j\$. The total distance they walk is the expression on the left. Since \$i<j\$ but \$l'_i > l'_j\$, they switch who is higher on the number line, which means they must cross at some point during their walks, call it \$p\$. But when they reach \$p\$, they could then swap their destinations and walk the same total distance. And then, it can't be worse for them to have walked to their swapped destinations from the start rather than using \$p\$ as a waypoint, which gives the total distance on the right-hand side.
So, sorting two out-of-order elements in \$l'\$ makes its distance to \$(1,2,...,n)\$ smaller or the same. Repeating this process will sort \$l\$ eventually. So, \$l\$ sorted is at least as good as \$l'\$ for any choice of \$l'\$, which means it as optimal or tied for optimal.
Note that the only property of \$(1,2,...,n)\$ that we used is that it's sorted, so the same algorithm would work to permute any given list to minimize its distance to any fixed list.
In the code, the only purpose of
z=zip(l,range(len(l))) is to make the input elements distinct, that is to avoid ties, while keeping the same comparisons between unequal elements. If the input we guaranteed to have no repeats, we could remove this and just have