题目思路

思路：思维,构造

考虑什么数需要更新位置？

先来考虑 $n$ 为偶数的情况：$mid = n/2$

记 $pos[x]$ 为数 $x$ 在数组中的位置

题目内容

宝石收藏家有一排 $n$ 颗珍贵的宝石，从左到右依次排列，每颗宝石都有一个独一无二的编号，分别是 $1$ 到 $n$。他希望将这些宝石按编号从小到大排列。

每次操作，他可以选择任意两颗宝石取出，然后将编号较小的那颗放在整个序列的最左端，编号较大的那颗放在最右端，其余宝石保持原有的相对顺序并向中间靠拢。

他想知道，最少需要多少次操作才能将宝石排列成 $1, 2, \dots, n$ 的顺序。

宝石的总数 $n$ 满足 $1 \le n \le 50000$，所有编号均为 $1$ 到 $n$ 的整数且互不相同。

输入描述

第一行包含一个整数 $n$，表示宝石的数量。 第二行包含 $n$ 个整数，依次表示初始时从左到右的宝石编号。保证这些编号是 $1$ 到 $n$ 的一个排列。

输出描述

输出一个整数，表示所需的最少操作次数。

样例1

输入

1
1

输出

0

说明

宝石序列仅有一枚，编号为 1，已经符合 $1$ 到 $n$ 的顺序，无需任何操作。 因此最少操作次数为 0。

样例2

输入

2
2 1

输出

1

说明

初始序列为 [2, 1]（$n=2$）。 选择编号 1 和 2 两颗宝石，将较小的 1 放到最左端，较大的 2 放到最右端，序列直接变为 [1, 2]。 因此最少操作次数为 1。 题解中偶数情况 $L=1,R=2$，$p_L = 1 > p_R = 0$，直接得到答案 $n/2 = 1$。

样例3

输入

3
2 1 3

输出

1

说明

初始序列为 [2, 1, 3]（$n=3$）。 一次操作即可完成排序：选择编号 1 和 3，将较小的 1 放到最左端，较大的 3 放到最右端，剩余的 2 自然留在中间，得到 [1, 2, 3]。 题解中奇数情况 $L=R=2$，计算得到答案为 1。

样例4

输入

5
5 4 3 2 1

输出

2

说明

初始序列为完全逆序 [5, 4, 3, 2, 1]（$n=5$）。 一种最优方案为两次操作： 第一次选择 1 和 5，1 放最左、5 放最右，序列变为 [1, 4, 3, 2, 5]； 第二次选择 2 和 4，2 放最左、4 放最右，序列变为 [1, 2, 3, 4, 5]。 题解中奇数情况 $L=R=3$，在位置 2 找到 3，向左扫描得到 $t=2$，向右扫描得到 $t=4$，最终 $\max(2,5-4+1)=2$。