All Tracks Algorithms Graphs Breadth First Search Problem

Permutation
/

Algorithms, Breadth-first search, Graph

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
通知
View All Notifications

?