P1698 [USACO18JAN] Out of Place B

题目描述

给出 $N$ 个数的序列 $A_i$ 。

每次可交换任意两数的位置。

要求通过最少的交换次数使得序列非递减。

输入格式

首先给出一个整数 $N$（$2 \leq N \leq 100$）。

下来 $N$ 个整数 $A_i \ (1 \le A_i \le 10^6)$ 。

输出格式

一行一个整数，即交换的最少次数。

输入输出样例 #1

输入 #1

6
2 4 7 7 9 3

输出 #1

3

说明/提示

2 4 7 7 9 3 - 原始队伍
2 4 7 7 3 9 - 交换
2 4 3 7 7 9 - 交换
2 3 4 7 7 9 - 交换