Tangled Electric Wires

Interview

Time limit1sMemory limit128 MB

Summary

Given a matching between left and right poles, find the minimum number of wires to cut so no two remaining wires cross, which reduces to computing N minus the longest increasing subsequence.

Level: Medium5 of 10
Topics: Dynamic programming, Binary search, Array
Solved: No attempts yet

Problem

In a city, utility poles stand in two rows along opposite sides of a road. Each wire connects one pole on the left side to one pole on the right side, and no pole is connected to more than one wire.

Many of the installed wires cross each other. Crossing wires can be dangerous, so some wires will be cut so that no two remaining wires cross.

Because the already installed wires should be preserved as much as possible, the number of cut wires must be minimized. Find the minimum number of wires that must be cut to remove all crossings.

Input

The first line contains the number of poles, N. (1 ≤ N ≤ 100,000)

Then N natural numbers are given. The i-th number indicates which pole on the right side is connected to the i-th pole on the left side. Each number is a natural number not greater than N.

Output

Print the minimum number of wires that must be cut so that no wires cross.

Examples1

Example 1
Input
```
4
2 3 4 1
```
Expected output
```
1
```