问题描述

有 $N$ 个高度不同的积木按照一列排列。进行一些操作，将相邻的两个积木交换位置，使得积木从最高的逐渐变低的顺序排列。具体而言，设交换后的第 $i$ 个积木的高度为 $Ai$，最高的积木的位置为 $T$ ，要求满足：

• $A1$ < $A2$ < ... < $AT$ > ... > $AN-1$ > $AN$

请计算需要进行的最小交换次数。

输入

输入数据从标准输入读取，具体格式如下。

$N$ $B1$ $B2$ ... $BN$

• 第一行为一个整数 $N$，表示积木的数量 $(1≦N≦10^5)$。
• 第二行为 $N$ 个整数，表示初始时积木的高度 $Bi$，按照它们的初始顺序给出。
• 积木的高度各不相同，即 $Bi≠Bj (i≠j)$。

输出

输出需要进行的最小交换次数。每个输出占一行，并进行换行。

部分点

本问题包含两个数据集，每个数据集最高可获得的分数已经给出。

• 对于满足 $N≦100$ 的数据集1，能够正确解决可得30分。
• 对于没有附加约束的数据集2，能够正确解决可得70分。

示例输入1

4
2 4 1 3

示例输出1

1

只需要一个交换即可变成满足条件的顺序。

示例输入2

5
2 4 1 3 5

示例输出2

3

一种需要三次操作的排序方式如下。

示例输入3

6
1 2 4 3 5 6

示例输出3

1