#P1967. 2024.8.31-JD-第2题-数字反转

2024.8.31-JD-第2题-数字反转

题目内容

给出一个nn个互不相同的非负整数，最初是无序的，现在有两种操作：

选择两个连续的数字，然后反转他们的位置，比如[1,21,2]会变成[2,12,1]

选择三个连续的数字，然后反转他们的位置，比如[1,2,31,2,3]会变成[3,2,13,2,1]

可以证明，在有限次以上两种操作下，一定可以将数列变为有序。但是如果一直进行第一种操作，那不就变成冒泡排序了吗，所以你要是最小化第一种操作的次数。

现在问在要把所有的数字变成升序的前提下，最少要进行多少次第一种操作？

输入描述

第一行输入一个正整数nn，代表数字的个数

接下来nn行，每行一个整数aia_i,保证这些数字互不相同

1≤n≤1051≤n≤10^5

0≤ai≤1090≤a_i≤10^9

输出描述

输出一个整数，代表最少进行的操作11的次数

样例1

输入

4
2
4
3
1

输出

1

说明

先对最后三个数字进行一次操作22，然后再对前两个数字进行一次操作11

知识点:*****

查看知识点以及同类型题目

Statistics