Woburn Challenge 2016-17 Round 3 - Junior Division

Problem 2: Pokéwarehouses

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 charging of planning out an upcoming shipment of N (1 ≤ N ≤ 10⁵) 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 ≤ S_i ≤ 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 Format

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..N).

Output Format

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.

All Submissions
Best Solutions

Point Value: 7 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Feb 19, 2017
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)