题目描述

小方块在祖父家度过寒假后回到了家。离开期间，他的朋友小三角玩过他的玩具。共有 $N$ 个玩具，编号为 $1,2,\ldots,N$。

为了不让小方块生气，小三角需要把玩具重新排列成：

最初，所有玩具以某个顺序排成一列，因此给定的是一个 $1\sim N$ 的排列 $P$。

小三角可以选择一个连续区间 $[i,j]$，将这个区间中的玩具按编号从小到大排序。该操作需要的时间为：

秒。

请计算将整个排列变为升序排列所需的最少总时间。

调用协议

你需要实现以下函数：

int solve(int N, int P[]);

该函数只会被调用一次。

• N 表示玩具数量；
• P 是一个从下标 $0$ 开始的数组，表示玩具的初始排列；
• 函数应返回将排列完全排好序所需的最少时间。

选手不应实现 main 函数。

样例 grader 的输入格式

样例 grader 从标准输入读取：

• 第一行一个整数 $N$；
• 第二行 $N$ 个整数，表示排列 $P$。

样例 grader 将 solve 的返回值输出到标准输出。

数据范围

• $1\le N\le4\times10^6$；
• $P$ 中 $1,2,\ldots,N$ 各出现恰好一次；
• $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数；
• 正式评测使用的 grader 不保证与下发的样例 grader 完全相同。

子任务

样例 1

输入：
5
3 1 4 2 5

输出：
2

样例说明

先将区间 $[0,1]$ 排序，耗时

排列变为：

1 3 4 2 5

再将区间 $[1,3]$ 排序，耗时

排列变为：

1 2 3 4 5

总耗时为 $2$ 秒，且这是最优答案。

样例 2

输入：
3
1 2 3

输出：
0

排列本来已经有序，不需要执行操作。

@下发文件