Permutation
/

## Algorithms, Breadth First Search, Graphs

Problem
Editorial
Analytics

Given a permutation of 1 to n, you need to perform some operations to make it into increasing order. Each operation is to reverse an interval $a_1,a_2,\dots,a_x(1\le x\le n)$ (a prefix). Your goal is to minimize the number of operations.

Input

The first line contains an integer $n$ ($1\le n\le 8$).

The second line contains $n$ space separated integers, representing the sequence $a$.

Output

An integer representing the answer, that is, the minimum number of operations needed to make the permutation into increasing order.

SAMPLE INPUT
3
3 1 2
SAMPLE OUTPUT
2
Explanation

A possible way is to reverse $[1,3]$, and then $[1,2]$.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...