题目思路

思路：思维,构造

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

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

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

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

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

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

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