2865: 「LibreOJ Round #6」花火

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:2 解决:0

题目描述

$n$ 个烟火排成一排,从左到右高度分别为 $h_1,h_2,\cdots,h_n$,这些高度两两不同。

每次 Yoko 可以选择两个相邻的烟火交换,这样的交换可以进行任意多次。

每次 Yoko 还可以选择两个不相邻的烟火交换,但这样的交换至多进行一次。

你的任务是帮助 Yoko 用最少次数的交换,使这些烟火从左到右的高度递增。

输入

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

第二行包含 $n$ 个正整数 $h_1,h_2,\cdots,h_n$,相邻整数之间用一个空格隔开。

输出

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

样例输入 复制

5
3 5 4 1 2

样例输出 复制

5

提示

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