Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS08PSG - Parallel Stripes Galaxy

The MathUniverse is full of strange places. Parallel Stripes Galaxy (PSG) is one of the oddest. Each colony in the PSG consists of two rows of inhabited buildings. Buildings in the first row are paired with buildings in the second row by connection channels which are line segments.

Intergalactic Security Organisation (ISO) needs to monitor the communication in some PSG colonies and has to prepare the budget for this operation.

Since the buildings lie on two parallel lines the connections between buildings intersect sometimes. When a listening device is mounted on a single connection channel, ISO is able to monitor this connection together with all connection channels intersecting it. Your task is to calculate the minimal number of listening devices necessary to monitor a given colony. The buildings in the first row are described by numbers from 1 to n, in ascending order. In the second row a building gets the number k when it is connected with the k-th building in the first row. Hence the description of the colony is the number n of buildings in each row and the list of building numbers in the second row (read in the same direction as the first row is oriented).

Illustration of the example

In the exemplary colony we have 8 buildings with the second row ordered as 3,2,6,1,7,4,8,5. Then the channel between buildings marked "1" intersects with three other channels, and so on. It is possible to pick 3 channels for the installation, for example 1, 7 and 8 or 2, 4 and 5. Installing only two devices will not be enough.

Input

The input is a description of the colony. The first line consists of a single number n (1 <= n <= 1000) - the number of buildings in each row of the colony. The second line consists of n pairwise different numbers m (1 <= m <= n) separated by single spaces.

Output

The output should contain a single number - the minimal number of listening devices that need to be installed in this colony.

Example 1

Input:
8
3 2 6 1 7 4 8 5

Output:
3

Example 2

Input:
5
1 2 3 4 5

Output:
5

Scoring

There will be 5 tests. Each test will be worth two points to form the total of 10 points.


Added by:Adam Dzedzej
Date:2009-02-14
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource: High School Programming League 2008/09

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.