Woburn Challenge 2016-17 Round 3 - Junior Division

Pokémarts are stores which are always stocked with useful items to help Pokémon trainers on their journeys. However, keeping Pokémarts sufficiently stocked is at least as difficult as catching Pokémon!

You've been placed in charge of planning out an upcoming shipment of $N$ $(1\le N\le {10}^5)$ items. The items are numbered from $1$ to $N$, and are currently arranged in a single stack in an initial warehouse $I$ such that the $i$-th item from the top is item number $S_i$ $(1\le S_i\le N)$. Your job is to ensure that they get transported to a certain destination warehouse $D$, and end up arranged in a single stack such that the $i$-th item from the top is item number $i$.

Unfortunately, items are only allowed to be moved in a particular fashion. The only type of operation which may be performed consists of taking a single item from the top of one warehouse's stack, and moving it to the top of another warehouse's stack. Items may never be moved away from warehouse $D$, and may never be moved back to warehouse $I$, as this would make it look like progress was not being made. Furthermore, each warehouse is only large enough to contain a single stack, and no stacks may be formed outside of warehouses. As such, in order to make the shipment possible to complete, you may ask for $0$ or more intermediate warehouses to first be constructed.

Of course, constructing entire warehouses is expensive, so you'd like to avoid doing so. As such, you'd like to determine the minimum number of intermediate warehouses which must be constructed, such that the shipment may then be completed successfully.

Input Specification

The first line of input consists of a single integer $N$.
$N$ lines follow, with the $i$-th of these lines consisting of a single integer $S_i$ (for $i=1\dots N$).

Output Specification

Output one line consisting of a single integer – the minimum number of intermediate warehouses required to complete the shipment.

Sample Input

3
3
1
2

Sample Output

1

Sample Explanation

With one intermediate warehouse $W$, the following sequence of actions may be performed:

• Move item $3$ from warehouse $I$ to $D$.
• Move item $1$ from warehouse $I$ to $W$.
• Move item $2$ from warehouse $I$ to $D$.
• Move item $1$ from warehouse $W$ to $D$.