IOI Zoo is famous for giraffes. There are ~N~ giraffes in IOI Zoo, numbered from ~1~ to ~N~ in ascending order of their heights. The heights of the giraffes are different from each other. There are ~N~ cages placed in a straight line, numbered from ~1~ to ~N~ from left to right. In each cage, a giraffe is living in it. The giraffe ~P_i~ is living in the cage ~i~.

Mr. APIO is the curator of IOI Zoo. He is worrying about the ratings of IOI Zoo in reviews. IOI Zoo receives low ratings for the reason that "the visual quality of the giraffes is bad." Precisely, when a visitor takes a picture of giraffes, the visitor chooses integers ~l, r~ ~(1 \le l \le r \le N)~ and takes a picture of the giraffes in the cages ~l, l+1, \dots, r~. Then, the visual quality of the giraffes becomes bad if both of the following conditions are satisfied.

• There is a giraffe in the picture which is taller than the giraffes in both ends of the picture. In other words, there is an integer ~k~ ~(l < k < r)~ satisfying ~P_l < P_k > P_r~.
• There is a giraffe in the picture which is shorter than the giraffes in both ends of the picture. In other words, there is an integer ~k~ ~(l < k < r)~ satisfying ~P_l > P_k < P_r~.

Mr. APIO will arrange the positions of the giraffes so that the visual quality of the giraffes does not become bad for any choice of ~l, r~ ~(1 \le l \le r \le N)~ when a visitor takes a picture. Since it takes a lot of work to move a giraffe from one cage to another cage, he wants to minimize the number of giraffes which are moved. Of course, after he finishes moving the giraffes, in each cage, a giraffe should be living in it.

Given information of the current positions of the giraffes, write a program which calculates the minimum number of giraffes which are moved. Since Mr. APIO arranged the current positions of the giraffes at random, you may assume that the values ~P_i~ ~(1 \le i \le N)~ are generated at random (See Generation of Input Data for details).

Input Specification

Read the following data from the standard input. Given values are all integers.

~N~

~P_1\ P_2 \dots P_N~

Output Specification

Write one line to the standard output. The output should contain the minimum number of giraffes which are moved.

Constraints

• ~1 \le N \le 8\,000~.
• ~1 \le P_i \le N~ ~(1 \le i \le N)~.
• ~P_i \ne P_j~ ~(1 \le i < j \le N)~.
• The values ~P_i~ ~(1 \le i \le N)~ are generated at random (See Generation of Input Data for details).

Subtasks

1. (10 points) ~N \le 7~.
2. (22 points) ~N \le 13~.
3. (27 points) ~N \le 300~.
4. (41 points) No additional constraints.

Generation of Input Data

In this task, except for Sample Input, there are ~10~ test cases which satisfy the constraints of Subtasks 1, 2, 3, 4. Also, there are ~10~ test cases which satisfy the constraints of Subtasks 2, 3, 4 only, there are ~10~ test cases which satisfy the constraints of Subtasks ~3, 4~ only, and there are ~10~ test cases which satisfy the constraints of Subtask ~4~ only. In total, including Sample Input, ~44~ test cases are used for grading. All ~44~ test cases for this task are generated in the following way.

1. First, choose ~N~ satisfying the constraints of each subtask.
2. Then, among the ~N! = 1 \times 2 \times \dots \times N~ permutations ~(P_1, P_2, \dots, P_N)~ satisfying the constraints, choose one permutation at random with equal probability and generate ~P_1, P_2, \dots, P_N~.

Sample Input 1

6
5 4 6 1 3 2

Sample Output 1

2

Explanation for Sample 1

There are ~6~ giraffes in IOI Zoo. From the left, the giraffes ~5, 4, 6, 1, 3, 2~ are living in the cages in this order. In this arrangement, if a visitor takes a picture for ~l = 2~, ~r = 5~, the visual quality of the giraffes becomes bad. The two conditions are satisfied as follows.

• The giraffe in the cage ~3~ is taller than the leftmost giraffe (= cage ~2~) in the picture and the rightmost giraffe (= cage ~5~) in the picture.
• The giraffe in the cage ~4~ is shorter than the leftmost giraffe (= cage ~2~) in the picture and the rightmost giraffe (= cage ~5~) in the picture.

If Mr. APIO moves the giraffe ~1~ from the cage ~4~ to the cage ~1~, and he moves the giraffe ~5~ from the cage ~1~ to the cage ~4~, the visual quality of the giraffes does not become bad for any choice of ~l,r~ when a visitor takes a picture. Mr. APIO achieves the goal by moving ~2~ giraffes. Since it is the minimum value, output ~2~.

This sample input satisfies the constraints of all the subtasks.

Sample Input 2

4
4 1 3 2

Sample Output 2

0

Explanation for Sample 2

There are ~4~ giraffes in IOI Zoo. From the left, the giraffes ~4, 1, 3, 2~ are living in the cages in this order. In this arrangement, the visual quality of the giraffes does not become bad for any choice of ~l,r~ when a visitor takes a picture. Mr. APIO does not need to move giraffes. Therefore, output ~0~.

This sample input satisfies the constraints of all the subtasks.

Sample Input 3

7
3 1 6 7 4 2 5

Sample Output 3

2

Explanation for Sample 3

For example, if Mr. APIO moves the giraffes so that the giraffes ~3, 5, 6, 7, 4, 2, 1~ are living in the cages in this order. Then, the visual quality of the giraffes does not become bad for any choice of ~l, r~ when a visitor takes a picture. Mr. APIO achieves the goal by moving ~2~ giraffes. Since it is the minimum value, output ~2~.

This sample input satisfies the constraints of all the subtasks.

Sample Input 4

13
8 5 6 13 4 2 11 3 9 1 10 7 12

Sample Output 4

6

This sample input satisfies the constraints of Subtasks 2, 3, 4.