Sleepy Cow Sorting

题目描述

农夫 John 正尝试在他的 $N$ 头奶牛（$1 \leq N \leq 100$）出发去牧场吃早餐前将它们排序。 奶牛方便地编号为 $1 \dots N$。

目前，奶牛按顺序 $p_1, p_2, p_3, \dots, p_N$ 站成一排，农夫 John 站在奶牛 $p_1$ 的前方。 他想重新排列奶牛，使它们的顺序变为 $1, 2, 3, \dots, N$，并且奶牛 $1$ 紧挨着农夫 John。

今天奶牛有点困，所以在任何时刻，唯一会听农夫 John 指令的是正对着农夫 John 的那头奶牛。 在一个时间步中，他可以指示这头奶牛沿着队列向后走 $k$ 步，其中 $k$ 可以是范围 $1 \ldots N-1$ 内的任意值。 她经过的 $k$ 头奶牛会慢慢向前走，给她腾出空间，让她插入到它们之后。

例如，假设 $N=4$，奶牛最开始的顺序如下： FJ: 4, 3, 2, 1 唯一会听 FJ 的奶牛是 $4$ 号。如果他指示她向后走 $2$ 步，则顺序随后会变为： FJ: 3, 2, 4, 1

现在唯一会听 FJ 的奶牛是 $3$ 号，因此在第二个时间步他可以给 $3$ 号奶牛下达指令，依此类推，直到奶牛排好序。 农夫 John 急于完成排序，这样他就能回农舍吃自己的早餐。请帮助他找到将奶牛排好序所需的最少时间步数。

输入格式

第一行输入包含 $N$。 第二行包含 $N$ 个用空格分隔的整数 $p_1, p_2, p_3, \dots, p_N$，表示奶牛的初始顺序。

输出格式

输出一个整数：如果农夫 John 采取最优策略，在 $N$ 头奶牛变为有序之前所需的时间步数。

4
1 2 4 3

3

提示

题目署名：Dhruv Rohatgi

标签: USACO|2019|Bronze

来源

USACO|2019|Bronze