VN-TST 2003 Problem 5

Let $A$ be the set of all permutations $a = (a_1, a_2, \ldots, a_{2003})$ of the 2003 first positive integers such that each permutation satisfies the condition: there is no proper subset $S$ of the set $\{1, 2, \ldots, 2003\}$ such that $\{a_k | k \in S\} = S.$

For each $a = (a_1, a_2, \ldots, a_{2003}) \in A$ , let $d(a) = \sum^{2003}_{k=1} \left(a_k - k \right)^2.$

I. Find the least value of $d(a)$ . Denote this least value by $d_0$ . II. Find all permutations $a \in A$ such that $d(a) = d_0$ .