Minimum Operations to Sort a Deck

You are given a deck of n cards where each card is uniquely numbered from 1 to n in some arbitrary order. Your task is to determine the minimum number of operations required to sort the deck in ascending order.

You are allowed to perform the following operations:

• Reverse Operation: Reverse any contiguous subarray of the deck.
• Swap Operation: Swap any two cards in the deck.

If the deck is already sorted, then no operation is required. Otherwise, if a single operation (either a reversal or a swap) can sort the deck, output 1. If neither of the single operations is sufficient, then it can be shown that at most 2 operations are needed, so output 2.

Formally, given a permutation p = [p₁, p₂, ..., p_n], you need to determine the minimum number k such that performing k operations (where an operation is defined as above) results in the deck being sorted in ascending order. All comparisons and required checks can be performed in O(n^2) time for the constraints in this problem.

Mathematically, if we let S be the sorted permutation (i.e. S = [1, 2, ..., n]), you must find the minimum k such that the deck can be transformed into S by applying operations as defined.

inputFormat

The input is read from standard input and consists of two lines.

• The first line contains an integer n (1 ≤ n ≤ 1000), the number of cards in the deck.
• The second line contains n space-separated integers representing the permutation of cards.

For example:

5
3 1 2 5 4

outputFormat

Output a single integer to standard output, which is the minimum number of operations required to sort the deck in ascending order.

For example, given the input above, the output should be:

2

## sample

4
1 2 3 4

0