Oh no! The students have gotten themselves out of order in line. Can you get them back into order?
They are conveniently named $$$1$$$, $$$2$$$, $$$3$$$, ... and $$$N$$$. District policy ensures $$$N\le 1,000$$$. However, the students want to be cool, so you can only swap two students if there is exactly 1 student between them. For example, if the line was $$$2$$$, $$$1$$$, $$$3$$$, you could swap students $$$2$$$ and $$$3$$$.
You want to get them into sorted order, meaning $$$1$$$, $$$2$$$, $$$3$$$, ... $$$N$$$. Is it possible to sort the students while making sure they all look like cool kids? If so, print the minimum number of swaps needed to sort them. If not, print $$$-1$$$.
On the first line, you are provided an integer $$$1\le N\le 1,000$$$. On the next line, there are $$$N$$$ space-separated integers describing the current arrangement of students. The number $$$i$$$ at the $$$j^\text{th}$$$ position means that student $$$i$$$ is currently standing at position $$$j$$$.
Print a single integer, $$$-1$$$ if it is impossible to sort the students and the number of swaps necessary otherwise.
55 4 1 2 3
3
Swap students $$$5$$$ and $$$1$$$ first, then students $$$5$$$ and $$$3$$$, and lastly students $$$2$$$ and $$$4$$$. They all end up in sorted order in $$$3$$$ swaps, and it can be shown that this is optimal.
