G. student
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ students standing in a line, and the $$$i$$$-th student from the left has an exam score of $$$a_i$$$.

A teacher wants to assess the learning situation of these students. Specifically, each time he can choose to check the score of the $$$i$$$-th student. If at least one of the following conditions is met, the student will leave the line:

  • In the current line, there exists a student to the left of the $$$i$$$-th student with a score not less than $$$a_i$$$, and there exists a student to the right with a score not greater than $$$a_i$$$.
  • In the current line, there exists a student to the left of the $$$i$$$-th student with a score not greater than $$$a_i$$$, and there exists a student to the right with a score not less than $$$a_i$$$.

The teacher wants as many students as possible to leave the line. Your task is to determine the minimum number of students remaining in the line in the end.

Input

The first line contains a positive integer $$$n$$$, representing the number of students.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ denotes the exam score of the $$$i$$$-th student.

$$$1 \le n \le 2 \times 10^5$$$, $$$1 \le a_i \le 10^9$$$

Output

A single integer, representing the minimum number of students remaining in the line.

Examples
Input
3
11 45 14
Output
3
Input
6
8 3 4 4 3 2
Output
2