# Splitting permutations into transpositions

Suppose we are given an array $\texttt{a[]}$ of $n$ non-negative integers. The algorithm should give back $\texttt{-1}$ if an integer appears more than once in $\texttt{a[]}$.

Otherwise we interpret $\texttt{a[]}$ as a permutation $\pi:\{0,\ldots, \texttt{max(a[])}\} \to \{0,\ldots, \texttt{max(a[])}\}$ sending $\texttt{i}$ to $\texttt{a[i]}$ for $\texttt{i} \in \{0,\ldots,n-1\}$, and $\pi(k) = k$ for $k\geq \texttt{length(a[])}$.

What could be an algorithm to write $\pi$ as represented by $\texttt{a[]}$ as a sequence of transpositions, and what is the complexity?