题目描述(ID:12221)
标题: 花火
标签: 数据结构 线段树
详情: n 个烟火排成一排,从左到右高度分别为 h1,h2,⋯,hn,这些高度两两不同。
每次 Yoko 可以选择两个相邻的烟火交换,这样的交换可以进行任意多次。
每次 Yoko 还可以选择两个不相邻的烟火交换,但这样的交换至多进行一次。
你的任务是帮助 Yoko 用最少次数的交换,使这些烟火从左到右的高度递增。
输入格式:
第一行包含一个正整数n。
第二行包含 n 个正整数 h1,h2,⋯,hn ,相邻整数之间用一个空格隔开。
输出格式:
输出一个整数,表示最少的交换次数。
提示: 对于所有数据,满足 1≤n≤300,000,1≤hi≤n,hi互不相同。
数据范围见上表。
样例:

输入

5
3 5 4 1 2

输出

5

解释

一开始,5 个烟火的高度依次为 3,5,4,1,2。
第 1 次,交换第 4 根烟火和第 5 根烟火,交换后烟火的高度依次为 3,5,4,2,1。
第 2 次,交换第 3 根烟火和第 4 根烟火,交换后烟火的高度依次为 3,5,2,4,1。
第 3 次,交换第 1 根烟火和第 2 根烟火,交换后烟火的高度依次为 5,3,2,4,1。
第 4 次,交换第 2 根烟火和第 3 根烟火,交换后烟火的高度依次为 5,2,3,4,1。
第 5 次,交换第 1 根烟火和第 5 根烟火,交换后烟火的高度依次为 1,2,3,4,5。
可以证明这是交换次数最少的方案。
登录并解答