High School Programming League Problems Archive

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

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.