Pyramid Array

题目描述

给你一个由 n 个互不相同的整数构成的数组。每一步，你可以交换任意两个相邻的值。 你想把数组变换为一个金字塔数组。这意味着最终数组先严格递增然后严格递减。也允许最终数组仅为递增或仅为递减。 求最少需要多少步？

输入格式

第一行输入一个整数 n：数组的大小。 下一行有 n 个互不相同的整数 $x_1,x_2,\dots,x_n$：数组的元素。

输出格式

输出一个整数：最少所需的步数。

4
2 1 5 3

1

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le x_i \le 10^9$ 样例解释：你可以交换前两个数，得到一个金字塔数组 [1,2,5,3]。

标签: CSES1747|附加题1

来源

CSES1747|附加题1