该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

传说宇宙诞生的时候，有 $n$ 根光柱传输着能量，柱子高度恰好是 $1\sim n$ 的排列。

狡猾的大便人打乱了这些光柱，企图破坏宇宙的平衡，现在第 $i$ 根光柱的高度为 $a_i$ 。

正义的石老板想要把光柱恢复原状，但他的力量实在太渺小了。

石老板可以发动两种魔法，但每次发动魔法都会使得石老板减少一年的寿命：

• @@@@魔法， 石老板可以选择两个相邻的光柱进行交换，这样的交换可以进行任意多次。
• $$$$魔法，石老板可以选择两个不相邻的光柱进行交换，但最多只能用一次，用多了会爆炸。

石老板还想多领几年养老金。请你找出一种方法，让石老板的寿命减少最少（即最少得交换次数），使这些光柱从左到右的高度递增。

输入格式

第一行包含一个正整数 $n$。

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，相邻整数之间用一个空格隔开。

输出格式

输出一个整数，表示最少的交换次数。

样例输入

5
5 4 2 3 1

样例输出

3

样例解释

一开始，$5$ 根光柱的高度依次为 $5, 4, 2, 3, 1$。

第 $1$ 次，@@@@ 交换第 $2$ 根光柱和第 $3$ 根光柱，交换后光柱的高度依次为 $5,2,4,3,1$。

第 $2$ 次，@@@@ 交换第 $3$ 根光柱和第 $4$ 根光柱，交换后光柱的高度依次为 $5,2,3,4,1$。

第 $3$ 次，$$$$ 交换第 $1$ 根光柱和第 $5$ 根光柱，交换后光柱的高度依次为 $1,2,3,4,5$。

可怜的石老板失去了三年寿命，可以证明这是交换次数最少的方案。

数据范围与提示

对于所有数据，满足 $1\le n\le 300,000，1\le a_i\le n$，$a_i$ 互不相同。