Problems
Correcting Cheeseburgers
Correcting Cheeseburgers
Cheeseburgers are serious business. They are the most delicious food on earth, but there is a lot of room for error when making a cheeseburger. Even otherwise capable cooks often mess up the order of the assembled ingredients.
The only correct order of ingredients between the buns is, of course, as following from top to bottom:
\begin{enumerate}
\item Ketchup & Mustard
\item Beef Tomato
\item Pickles
\item Red Onions
\item Cheddar Cheese
\item Garlic
\item Salt & Pepper
\item Beef Patty, medium grilled
\item Corn Salad
\item Mayonnaise
\end{enumerate}
Any deviation from this order is completely unacceptable. Therefore it is sometimes necessary to reassemble a cheeseburger.
Space on an average plate and social norms are rather restrictive when it comes to operating on a cheeseburger. The only feasible operation is the bit-shuffle (burger-ineptly-transformed). The bit-shuffle separates the entire burger into four parts of contiguous ingredients $a, b, c$ and $d$ and arranges them in the new order $c~a~d~b$. The size of each of the four parts is selectable and may be zero.
Since the burger cools rapidly we are interested in the minimum required bit-shuffles to arrive at an acceptable burger.
Each given cheeseburger consists of $n$ unique ingredients labeled from $1$ to $n$. The correct order is always the natural order $1~2 ... n$.
\InputFile
First line contains the number $n~(1 \le n \le 10)$ of ingredients used. Second line contains $n$ integers describing the order of the ingredients of the given cheeseburger. The ingredients are numbered from $1$ to $n$.
\OutputFile
Output the minimum number of bit-shuffles to correct the given cheeseburger.
\Note
Illustration of the first sample input:
\includegraphics{https://static.e-olymp.com/content/6d/6da182196b26ca417c4eaf6bb28cc09283206ebb.gif}
Illustration of the second sample input:
\includegraphics{https://static.e-olymp.com/content/46/46f7a9ac3ebe701f909aeccb4433a1f0215eab51.gif}
Input example #1
9 3 4 7 8 9 1 2 5 6
Output example #1
1
Input example #2
3 1 3 2
Output example #2
1