#P17929. Increasing Swaps

Increasing Swaps

Increasing Swaps

给定 1,2,…,N1,2,\ldots,N 的排列 PP。你可以选择一个长度为 N−1N-1 的正整数序列 TT。

操作从第 11 次开始编号。在第 tt 次操作中,将所有满足 Ti≤tT_i\le t 的下标 ii 按升序排列,然后依次交换 PiP_i 和 Pi+1P_{i+1}。同一次操作中的交换按顺序执行,后面的交换使用前面的交换完成后的排列。

对于固定的 TT,定义 f(T)f(T) 为使 PP 变为升序排列所需的最少操作次数(允许为 00);如果永远不能排序,则定义 f(T)=10100f(T)=10^{100}。

求所有合法 TT 中 f(T)f(T) 的最小值。可以证明,题目范围内一定存在使 f(T)<10100f(T)<10^{100} 的 TT。

输入格式

N
P_1 P_2 ... P_N

输出格式

输出一个整数,表示答案。

数据范围

2≤N≤50002\le N\le5000,PP 是 11 到 NN 的排列。所有输入均为整数。

原比赛另设 N≤400N\le400 的部分分;本数据包使用完整范围、整题计分。

样例 1

输入:

4
4 2 1 3

输出:

2

样例 2

输入:

20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14

输出:

39