JOI, who enjoys gardening, grows a plant called "IOI grass" in his field every year. His field is divided into $N$ plots arranged in an east-west direction, numbered from 1 to $N$ starting from the west. There are $N$ plants in total, with one plant in each plot. The IOI grass planted in plot $i$ grows to a height of $h_i$ in the spring and does not grow further after that.

When JOI went to check on his field in the spring, he noticed that the arrangement of the IOI grass was different from what he had planned. IOI grass is a plant that requires a lot of sunlight. For any IOI grass planted in a certain plot, if there is an IOI grass taller than it in both a plot with a smaller number and a plot with a larger number, that IOI grass will wither before summer. In other words, to ensure that no IOI grass withers, the following condition must be satisfied:

• For every integer $i$ such that $2 \le i \le N-1$, at least one of the following two conditions holds:
  • For all integers $j$ such that $1 \le j \le i-1$, $h_j \le h_i$.
  • For all integers $k$ such that $i+1 \le k \le N$, $h_k \le h_i$.

Since IOI grass is very expensive, JOI decided to rearrange the IOI grass so that none of it withers. Because IOI grass is very large and delicate, JOI can only swap two adjacent IOI grasses. That is, in one operation, JOI can choose any plot $i$ ($1 \le i \le N-1$) and swap the IOI grass in plot $i$ with the IOI grass in plot $i+1$. As summer approaches, the possibility of them withering increases, so he wants to know the minimum number of operations required to ensure that no IOI grass withers.

Subtasks

Given the number of plots in JOI's field and the information about the height of each IOI grass, write a program to find the minimum number of operations required to rearrange them so that no IOI grass withers.

Input

Read the following from standard input:

• The first line contains an integer $N$, representing the number of plots in JOI's field.
• The following $N$ lines contain information about the heights of the IOI grass. The $i$-th line ($1 \le i \le N$) contains an integer $D_i$, representing the height of the IOI grass planted in plot $i$ in the spring.

Output

Output the minimum number of operations required as an integer on a single line.

Constraints

All input data satisfies the following conditions:

• $3 \le N \le 300\,000$.
• $1 \le D_i \le 1\,000\,000\,000$.

Subtasks

1. (10 points) $N \le 8$ satisfies.
2. (20 points) $N \le 20$ satisfies.
3. (15 points) $N \le 5\,000$ satisfies.
4. (55 points) No additional constraints.

Examples

Input 1

6
2
8
4
5
3
6

Output 1

3

Input 2

5
4
4
2
4
4

Output 2

2

Note 2

You can move the IOI grass in plot 3 to plot 1 or plot 5.

Input 3

4
1
3
4
2

Output 3

0

Note 3

In this example, there is no need to perform any swap operations.