JOI 君的爱好是家庭菜园，他每年都会在自己的田里种植一种名为“IOI 草”的植物。JOI 君的田地被分成了 $N$ 个东西向排列的区域，从西侧开始依次编号为 $1$ 到 $N$。总共有 $N$ 株 IOI 草，每个区域各种植一株。种植在区域 $i$ 的 IOI 草在春天会长到高度 $h_i$，之后便不再生长。

春天到了，JOI 君去查看情况时，发现 IOI 草的排列与预想的不同。IOI 草是一种需要充足阳光的植物，对于种植在某个区域的 IOI 草，如果其西侧（编号较小）和东侧（编号较大）的区域中都有比它更高的 IOI 草，那么这株 IOI 草在夏天到来之前就会枯萎。也就是说，为了保证没有任何一株 IOI 草枯萎，必须满足以下条件：

• 对于所有满足 $2 \le i \le N-1$ 的整数 $i$，以下两个条件中至少有一个成立：
  • 对于所有满足 $1 \le j \le i-1$ 的整数 $j$，满足 $h_j \le h_i$。
  • 对于所有满足 $i+1 \le k \le N$ 的整数 $k$，满足 $h_k \le h_i$。

由于 IOI 草非常昂贵，JOI 君决定对 IOI 草进行重新排列，以确保没有任何一株 IOI 草枯萎。IOI 草是非常巨大且脆弱的植物，JOI 君只能交换相邻的两株 IOI 草。也就是说，在一次操作中，JOI 君可以任意选择一个区域 $i$ ($1 \le i \le N-1$)，交换区域 $i$ 和区域 $i+1$ 的 IOI 草。随着夏天临近，枯萎的可能性会增加，因此他想知道为了使所有 IOI 草都不枯萎，所需的最少操作次数。

Figure 1. IOI 草的初始排列

输入格式

从标准输入读取以下内容：

• 第 $1$ 行包含一个整数 $N$，表示 JOI 君田地的区域数量。
• 接下来的 $N$ 行包含有关 IOI 草高度的信息。其中第 $i$ 行 ($1 \le i \le N$) 包含一个整数 $D_i$，表示春天时种植在区域 $i$ 的 IOI 草的高度。

输出格式

将所需的最少操作次数作为一个整数输出到标准输出。

数据范围

所有输入数据满足以下条件：

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

子任务

• 子任务 1 [10 点]：满足 $N \le 8$。
• 子任务 2 [20 点]：满足 $N \le 20$。
• 子任务 3 [15 点]：满足 $N \le 5\,000$。
• 子任务 4 [55 点]：无附加限制。

样例

输入格式 1

6
2
8
4
5
3
6

输出格式 1

3

输入格式 2

5
4
4
2
4
4

输出格式 2

2

说明

可以将区域 $3$ 的 IOI 草移动到区域 $1$ 或区域 $5$。

输入格式 3

4
1
3
4
2

输出格式 3

0

说明

在此样例中，无需进行任何交换操作。