1831. 冒泡～排序
时间限制：1000 MS 内存限制：128 MB
题目描述
## 题目描述 给出一个 $n$个互不相同的非负整数，最初是无序的，现在有两种操作： 1. 选择两个连续的数字，然后反转他们的位置，比如$[1,2]$会变成 $[2,1]$ 2. 选择三个连续的数字，然后反转他们的位置，比如 $[1,2,3]$ 会变成 $[3,2,1]$ 可以证明，在有限次以上两种操作下，一定可以将数列变为有序。但是如果一直进行第一种操作，那不就变成冒泡排序了吗，所以你要最小化第一种操作的次数。 现在问在要把所有数字变成升序的前提下，最少要进行多少次第一种操作？ ## 输入格式 第一行输入一个正整数 $n$，代表数字的个数 接下来 $n$ 行，每行一个整数 $a_i$，保证这些数字互不相同 $1 \le n \le 10^5$ $0 \le a_i \le 10^9$ ## 输出格式 输出一个整数，代表最少进行的操作1的次数 ## 输入 ```in1 4 2 4 3 1 ``` ## 输出 ```out1 1 ``` ## 提示 先对最后三个数字进行一次操作$2$，然后再对前两个数字进行一次操作$1$